Slashdot Mirror
Quantum Computing Not an Imminent Threat To Public Encryption
Bruce Schneier's latest blog entry points out an interesting analysis of how quantum computing will affect public encryption. The author takes a look at some of the mathematics involved with using a quantum computer to run a factoring algorithm, and makes some reasonable assumptions about the technological constraints faced by the developers of the technology. He concludes that while quantum computing could be a threat to modern encryption, it is not the dire emergency some researchers suggest.
Uff, I meant Applied Cryptography . Practical Cryptography is a bit too basic an overview written with a co-author.
I'm afraid you'll have to look those physics books back up.
Although QM computers do use basic entanglement for creating superpositions, understanding Shor's algorithm (the one everyone is concerned about since it's factoring in polynomial time) is mostly just understanding QM superposition. Entanglement gives generic QM computers great parallel processing power by superposition by explaining how QM probability wave combine under superposition, but Heisenberg limits the computing power of a QM computer in a non-trivial way as well because after you collapse the wave functions by measurement you give up the parallel processing enabled by Entanglement (e.g., if you peek inside the oven, it stops working, if some of the heat leaks out of the oven even with the door closed, it doesn't work as efficiently, the oven being the QM computer).
FWIW, Shor's algorithm essentially converts factoring into a sequence period finding exercise. You might imagine that that's something easy to do if you had a machine which given a bunch of superimposed waves with a certain modulo structure could tell you the period (hint the ones that don't modulo with a specific period with self interfere and measure as zero, where the one with that period with self-reinforce). With a QM computer you do this all in parallel with superimposed probability waves and when you measure it, the highest probability one you measure is the one that doesn't self-interfere (the ones that self-interfere has probability near zero). Basically this measurement is wave function collapse which doesn't actually depend on entanglement or heisenberg to understand (although it does require you to believe in QM wave functions and measurement operators).
Entanglement is really a strange artifact of QM that explains probability correlations that you see in QM experiments that can't be explained classically. It's really more of an artifact of the existance of probability amplitude waves (the QM wave function) rather than an effect that directly enables the QM computer. Of course if you didn't have QM wave functions you wouldn't have a QM computer so I guess that's a chicken and egg scenario. Entanglement is like the "carburator" function of the QM computer. The QM computer uses superposition of QM wave functions to work and when you have more than one QM wave function, they get entangled when you start superimposing wave functions and the way the waves entangle helps you compute in parallel so it's important to understand how these waves entangle.
Heisenberg's principle is a consequence of wave function collapse (measurement) which also limits the QM computer (this limiting effect is often called QM de-coherence). Heisenberg isn't required by a QM computer when it's computing, but you need to see the result somehow so when you measure the result, one of the side effects is the Heisenberg principle (although that's also a chicken-egg problem, since HP is a consequence of QM wave function collapse and w/o QM there's no superposition computing). The closest explanation I can think of is that Heisenberg's principle is the "heat" caused by friction of the QM computer. You need friction to stop the computer to read out the result, but at the same time you can't get rid of a little friction while it's running either (causing de-coherence). The side effect of this friction is heat.
You may have a personal opinion that superposition is a "nice way of doing statistics using discrete values for covering the not so discrete results of experiments", but there is experimental evidence that your personal opinions is at odds with physical reality. As QM computers that do QM computing (including IBM's NMR experiment which implemented shor's algorithm) have already been implemented it's hard to refute that something non-classical is going on.
It may be that in the end, QM is total malarky and there's some other weird unexpected thing going on, but there are mountains of evidence that whatever is going on, it isn't as simple as "hidden variables"