John S. Denker wrote: >3) A sufficiently well designed quantum computer can, >in principle, find some needles in some haystacks, >precisely because the structure of the machine, acting >according to the laws of quantum mechanics, does in fact >"collapse" the wave-function into a representation of >the wished-for answer.
Sure, but your description could be a bit misleading for the uninformed (which is what this thread is for, after all). The original poster seemed to have the misconception that, if I can just describe some set S of states, a quantum computer can somehow magically cause any superposition to collapse onto a state S. Well, this is occasionally true, but more often it is just plain wrong. Just because you can describe a special set of lucky states doesn't mean you can set up a superposition of the required form to collapse into one of these lucky states in O(1) quantum operations. Quantum computers are not a magic device for solving all search problems in constant time. The reality is much more complicated. Some might think that Shor's factoring algorithm is a counterexample. After all, if you read a popular exposition, it might seem like it sets up a superposition of all integers less than n, then checks in parallel which ones divide n, and somehow causes the wavefunction to collapse onto one state containing a divisor d of n. Well, that's probably a misleading way to think about Shor's factoring algorithm. In fact, what Shor's algorithm does is set up a superposition so that collapsing to a random state in the superposition will, with high probability, give you useful information about the factors of n. All the hard work, and technical insight, is in seeing how one can set up such a superposition using only the basic primitives available in a quantum computer (namely, unitary transformations). As you can see, even in Shor's algorithm, what we have is a collapse of the superposition onto a random state. (Of course, the notion of "random" is not necessarily the uniform distribution -- it is weighted appropriately, according to the amplitude of the wavefunction at the appropriate points -- but it is still random.) If you want to find a needle in a haystack, you have to identify some way to set up a superposition so that random collapse will give you the needle with high probability. Let me stress that setting up the desired superposition is the hard part. And, for the example given by the poster -- exhaustive keysearch -- there is no way known to set up a superposition of the desired form with O(1) basic quantum operations. In fact, there is not even a shred of reason to believe such a quantum algorithm might exist; all available evidence points to the contrary. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]