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 [EMAIL PROTECTED]