From: Hal Finney (hal@rain.org)
Date: Fri Feb 07 1997 - 22:38:22 MST
At <URL: http://jya.com/qshake.htm > is a reprint of the article by
cryptographer Giles Brassard from the Jan 31 1997 issue of Science
about Grover's quantum search algorithm we have discussed here recently
and its application to crypto.
Here is an excerpt, describing how it could be used to find an entry in
a directory of names and phone numbers which matches a given phone number:
To solve the database search problem, Grover starts by setting a
quantum register to a superposition of all possible names in the
phone directory. A single access to the database (which may involve a
computation if it is virtual) creates a superposition of all possible
pairs of matching names and phone numbers. The resulting quantum state
contains the desired pair, but with vanishingly small amplitude -- the
measure of how much it contributes to the global state -- compared to
the multitude of unwanted pairs. If the register were observed at that
point, the odds of obtaining the relevant answer would be as small as
if an arbitrary name had been tried at random by a classical computer.
Grover's discovery is a clever sequence of simple operations on the
register's state. This process can be thought of as a sort of "quantum
shake," which, contrary to a classical shake, brings order rather than
disorder. Just as crests reinforce each other when ripples meet in water,
Grover's shake uses quantum interference effects to increase the amplitude
of the pair that contains the target phone number at the expense of
all other pairs. This increase is so subtle that the probability of
obtaining the desired result by observing the quantum register after
a single shake is almost as small as before. However, the shake can be
repeated over and over again, gradually boosting the amplitude of the
correct answer to a detectable level. Provided the solution is unique,
it is found with near certainty if the quantum register is observed after
(pi/4)N1/2 shakes, where N is the size of the database.
To use an analogy from Kristen Fuchs, Grover's quantum searching
technique is like cooking a souffle. You put the state obtained by
quantum parallelism in a "quantum oven" and let the desired answer
rise slowly. Success is almost guaranteed if you open the oven at
just the right time. But the souffle is very likely to fall -- the
amplitude of the correct answer drops to zero -- if you open the oven
too early. Furthermore, the souffle could burn if you overcook it:
strangely, the amplitude of the desired state starts shrinking after
reaching its maximum. After twice the optimal number of shakes,
you are no more likely to succeed than before the first shake.
It does not go into more detail about Grover's algorithm than this but
I thought that was a nice bit of imagery. Who knows what the quantum
theorists will cook up next?
Hal
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:44:09 MST