First: Don't panic. So far no usable quantum computer has been built. It will be a long time before one is. Secondly a quantum computer capable of factoring 1024 bit keys will require polynomially high precision in its extremely tiny components, whereas a classical computer will only require order one precision, regardless of the number of bits. This may well not be feasible until we are close to achieving nanotechnology. (That is polynomially high precision, which achievable. Non polynomially high component precision is of course impossible for problems large enough to be interesting) Secondly: Yes, quantum computers will indeed be able to solve in polynomial time many problems that require non polynomial time for classical computers. In plain English that means that they can solve problem classes that ordinary computers cannot solve. Factoring is one of those problems. This result was established by E. Bernstein and U. Vazirani, and has recently been published as: Quantum Complexity Theory, Proc. 25th ACM Symp. on Theory of Computation, pp. 11--20 (1993). Barak Pearlmutter summarizes the current status as follows: The class of things a quantum computer can compute in polynomial time is called QRP. The class of things a regular randomized computer can compute in polynomial time is called RP. It is not known whether RP>P. But, under the usual assumptions, we know RP < QRP <= P^#P. It is not known whether QRP < NP. Factoring has not been shown to be in RP, nor has it been shown to be NP-complete. (If factoring were shown to be NP-complete, then we would have NP=coNP, a big deal, and also NP <= QRP, an immense deal assuming that accuracy problems don't make them impossible to build.) So it might be that NP <= QRP. Also plausible is RP < QRP < NP. In any case, the public key cryptosystems we thought were secure (RSA, discrete logs) has now had their viability brought into serious question. Even if QRP<NP (which it might not be) it might be the case that any public key cryptosystem can be broken in QRP, since no public key cryptosystem has been exhibited for which the inverse problem is NP-complete. (Some have been related to NP-complete problems, but with the reductino in the wrong direction, which proved fatal.) I will shortly give a hand waving explanation of why it is so, why a quantum computer is potentially capable of solving problems that a classical computer cannot solve within the lifetime of the universe. I am not able to cite Shor's result, showing that factoring is among the problems that a quantum computer can solve efficiently, because he is not yet published. I am attempting to reconstruct his results from information that people have given me about them, but so far I am making fairly heavy weather of it. He is applying the remarkable result of Bernstein and Vazirani to a particular interesting case. So if you want to go an prove that his method cannot possibly work, simply go and prove that the methods of Bernstein and Vazirani, cannot possibly work. The quantum magic part is in Bernstein and Vazirani's work, not Shor's work. (I can assure that they will work.) Some of you folk may remember the great flame war on this topic on the Extropians mailing list. I mentioned this result, without giving source or authority (it had not been published to my knowledge at that time), and Price flamed me vigorously, calling me an idiot, an ignoramus, a crackpot, and a fool, and so forth, and offered to bet 5000 British pounds, then about US$7500, on the matter. $7500 bet! I of course cheerfully accepted. Alas I wanted the judging to be done by somebody who had published on quantum computing in a refereed journal, (like Bernstein) and I wanted that person to hold the pot. Michael reluctantly agreed to having the bet judged by a qualified person but he wanted the pot held by a bunch of people who are involved in a business concerning which I have very grave and serious suspicions. I attempted my various means of persuasion to get him to put up the pot. Alas, Michael was not willing to let the pot for the bet go outside the control of him or these dubious people. Eventually I resorted to a vigorous attempt to shame him into putting up the money. My unkind comments concerning Michael and his pals eventually resulted in me being expelled from the Extropians list, for flaming Michael and defaming the Exi board. But since Bernstein and Vazirani are now published, and no further suckers seem willing to come forward and bet, I am now going to give an vague hand waving explanation of their results. A quantum event has many outcomes, all of them happening at once. Consider a quantum computer with 1024 bits of memory. (128 bytes, not 128 megabytes) A classical computer can only be in one state at a time. A quantum computer can be, and usually will be, 2^1024 states simultaneously. That is 10^306 states, or about 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 states simultaneously. Obviously a quantum computer can explore state space a lot more efficiently than a classical computer can. In fact a classical computer simply cannot explore a space that big, even if the computer were to fill then entire universe. This however is not much use, because the probability of observing it in the correct state is equally low. The clever trick of Bernstein Vazirani is to arrange for constructive interference between correct answers and destructive interference between incorrect answers. This requires the quantum computer to retain quantum coherence. It is evident that most of the people blowing off and saying "Quantum computers are bullshit" do not understand quantum coherence etc. (At least Michael Price had some faint grasp of quantum mechanics.) Thus a quantum computer has vast potential for problems that involve the combinatorial explosion. Unfortunately, because the transformation is unitary, a quantum computer cannot efficiently report back the one correct result that it has discovered to the any one particular reality Although getting the information out of a quantum computer is inherently inefficient, it is not always nonpolynomially inefficient. My judgment, for what it is worth, is that (for the vast majority of problems that are not NP complete, but are NP and are actually interesting, because they have an answer that is true rather than an answer that is marginally better than other answers) it will be reasonably easy to find ways of persuading a quantum computer to disgorge the necessary information that are only polynomially inefficient. These methods will be extremely general, rather than domain specific, and algorithms will improve in the direction of generality. A quantum computer will always operate very rapidly, for any algorithm that one would wish to program on a quantum computer. For many algorithms, the probability of it emitting the right answer is rather low. If the probability is non polynomially low, then the algorithm is of course useless. A number of algorithms have now been shown, including factoring, where the probability is only polynomially low, which is of course enormously better than non polynomially low. The precision of the components of the quantum computer must be proportional to the time taken by one shot of the algorithm, since in order to get the information out of the computer with a reasonably high probability, we require the class of true answers to interfere constructively, while the vastly larger class of incorrect answers interferes destructively. If the computer sits there for too long, random thermal noise will destroy coherence, and all the answers will interfere randomly, so the probability of getting the right answer out (observing the computer in the desired state) will be non polynomially low. Similarly, if the quantum computer takes too many steps, imperfections in its components will destroy quantum coherence. When the coherence is lost, a quantum computer is equivalent to a non deterministic computer. When it retains quantum coherence, it can surpass a non deterministic computer by an exponentially large factor. --------------------------------------------------------------------- We have the right to defend ourselves and our | property, because of the kind of animals that we | James A. Donald are. True law derives from this right, not from | the arbitrary power of the omnipotent state. | jamesd@netcom.com