Quantum computers inch closer?

[David Wagner]

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 majordomo at wasabisystems.com