Doubts about efficiency of Shor's factoring algorithm in quantum computers

[Ray Perlner]

I can't say I entirely followed this paper, but I'm pretty sure that the
paper neglects to take into account the fact that you can move to more
aggressive error correction as the computer scales up. e.g. rather than just
having each logical qbit encoded as 7  physical qbits, you could have each
logical qbit encoded as 7 sub-logical qbits which are in turn represented by
7 logical qbits. From the simulation  graph he gives, he can get an error
rate of 10^-9 per operation in his logical qbits even with a rate of 10^-5
per operation on the physical qbits. I see no reason why a similar
improvement wouldn't be possible with another round of encoding, or merely a
more agressive code that can correct for multiple physical q-bit errors.

Aside from that, I'm frankly not too impressed with the paper --  the author
confuses 256-bit RSA with 256-bit ECC for example. Quantum computing is
still quite a ways off, if nothing else for dumb economic reasons, but this
paper doesn't really do much to convince me that it isn't a real possibility
that we need to be worried about in the long term.

On Mon, Apr 28, 2008 at 5:57 PM, Perry E. Metzger <perry at piermont.com>
wrote:

>
> Charles McElwain <charlesmcelwain1 at verizon.net> writes:
> > Follow-ups on this line of research will be interesting for the
> > evaluation of any impact of quantum computers on cryptography, and
> > even generally, since the decoherence behavior would tend to make
> > quantum computers approximate improving classical computers.
>
> Very interesting indeed. I'd be curious about the opinions of people
> who know the field well. My QM and quantum computing knowledge aren't
> quite up to the task of analyzing the paper.
>
> > From the Physics pre-print server arXiv, quantum physics section:
> > http://arxiv.org/abs/0804.3076
>
> Perry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com