Shor's algorithm in danger?

[Rod Van Meter]

Hi,

I saw the the email concerning Shor's algorithm to me.  I want to
respond to it, before the meme that Shor's algorithm has been
discredited takes root.

In one sentence, my position on Shor's algorithm:

* There are very good reasons to take a Missouri "show me" attitude
  toward Shor's algorithm, but this paper probably does not change the
  arguments, and a variety of people much smarter than me have
  analyzed the algorithm in more detail and are pretty convinced it's
  going to work with acceptable scaling.

A one-sentence summary of the paper:

* Quantum error correction doesn't work.

In order to believe that Shor doesn't work, you have to believe that
either the algorithm fundamentally doesn't scale, or that quantum
error correction doesn't work.

Or, conclude that the paper is in error for some reason.  I think it's
likely that the authors have inferred too much from a relatively
limited set of experiments.

Essentially, what they have done is a simple simulation of an
imperfect inverter and extrapolated from that to the performance of a
complete system.

If someone handed you an unrefereed tech report that said,
"Transistors are noisy, so a microprocessor can't work," would you
believe it?  Today, of course not, but even forty years ago your first
response would probably have been to seek out the opinion of an
expert, or wait for the paper to be refereed before bothering with it.
With quantum computers, we don't yet have a working, large-scale
machine, but would you prefer to believe a set of papers already
vetted by smart people, or an unrefereed one?

I don't mean to disparage the authors; I know neither of them
personally, but the second author, at least, has done good work.  But
this paper, I think, is questionable.

In summary, the paper in question (arXiv:0804.3076) would have broad
implications for the ability of quantum computers to maintain state
accurately enough to provide real-world acceleration over classical
computers. It's a very legitimate concern, which gets raised
occasionally by very smart people, and usually ends in a stalemate
with the preponderance of quantum information people on the side of
"don't worry, QEC works". But it's not yet clear that this paper
really pushes the argument forward in either direction. The paper is
also not yet refereed, and it will be interesting to see how it
changes as a result of any referee's comments.

The authors may turn out to be right.  More power to them in
attempting to prove it; right or wrong, these arguments are often
illuminating.  Meantime, for all but a handful of people, we now
return you to your regularly scheduled programming.

I put a longer post, with references, on my blog at
http://rdvlivefromtokyo.blogspot.com/2008/04/shors-algorithm-in-danger.html

In the hopes that someone finds this useful,

		--Rod

-- 
Rodney Van Meter
Assistant Professor of Environment and Information Studies
Keio University, Shonan Fujisawa Campus, Japan
http://web.sfc.keio.ac.jp/~rdv/


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com