What's a Quantum Phone Book?
Today's Innovators
Murray Hill, N.J.  A phone book might seem like an unlikely place
to apply the principles of quantum mechanics. But a Bell Labs researcher
has attracted international attention with an algorithm that could
produce a drastic improvement in searching all kinds of databases,
including a phone directory where the names can be arranged randomly 
instead of alphabetically.
Don't look for quantum Yellow Pages anytime soon, however. Lov K.
Grover's search mechanism awaits the invention of a quantum
computer.
"It will speed up any kind of database search," Grover
said. "However the maximum advantage is gained in unsorted
databases." The algorithm could someday be used to speed up a wide
range of problems that are solved by massive searching.
A Contribution to Quantum Complexity
Grover, who works in Advanced Technologies, did the work on the
algorithm on the side in addition to his normal job of designing and
implementing CAD circuit simulators. Grover has long had an interest in
probabilistic algorithms. He got involved with quantum computing in 1994
after hearing about a powerful factoring algorithm developed by AT&T
Labs researcher Peter Shor.
Grover
"I think it's a very nice piece of work," Shor, one of the
pioneers of quantum computing, said of Grover's algorithm. "It's
one more thing you can do on a quantum computer."
The quantum search algorithm also has earned the praise of Caltech
physicist John Preskill, one of the world's leading experts in quantum
mechanics. Preskill called Grover's algorithm for searching an unsorted
database "perhaps the most important new development" in
quantum complexity.
"If quantum computers are being used 100 years from now, I would
guess they will be used to run Grover's algorithm or something like
it," Preskill says.
To Be and Yet Not to Be
The key to Grover's search mechanism lies in a quantum computer's
ability to exist in more than one state at a time, and search different
parts of the database at the same time. A classical computer has bits
that exist in a state of one or zero, but a quantum computer's
"qubits" (for quantum bits), exist in a state of one and zero
simultaneously.
"If you have an unsorted database with a million records in it,
a classical computer would have to look at a substantial fraction of
records, maybe half a million," Grover explains. "A quantum
computer would need a very, very small number of steps to get the same
result."
The number of steps needed in Grover's algorithm is defined by the
square root of the number items in the data base. For instance, in a
database with a million entries, a quantum computer would need only
1,000 steps to find the correct solution.
Wrong Answers Cancel Out
To solve the problem, Grover starts by setting a quantum register to
a superposition of all possible items in the database. The quantum state
contains the right answer, but if the register were observed at this
point, the odds of picking the right answer would be as small as if one
picked the item by random.
Grover's discovery involves a sequence of simple quantum operations
on the register's state. He describes the process in terms of wave
phenomena. "All the paths leading to the desired results interfere
constructively, and the others ones interfere destructively and cancel
each other out," Grover explains.
The algorithm makes use of counter intuitive and sometimes bizarre
principles of quantum mechanics. "Programming a quantum computer is
particularly interesting since there are multiple things happening in
same hardware simultaneously," Grover said. "One needs to
think like both a theoretical physicist and a computer
scientist."
Algorithm Is Getting Attention
Since he presented his algorithm at a computer science conference in
Philadelphia last year, Grover's work has attracted the attention of
many physicists and computer scientists. More than a dozen technical
papers have been written on it. Grover has also been mentioned in
Science, Science News, The
Economist and Physics Today.
"It's been a pleasant surprise," Grover said. Despite the
attention given his work, those involved with quantum computing don't
expect to see the machines built soon.
"We won't see a quantum computer for a long time," Shor
contends. "I'm pretty sure we're going to see small quantum
computers that can prove this is the way the universe works. Whether
we're going to see a quantum computer that's capable of solving big
problems is another question."
Grover notes, too, that computer science historically has moved much
faster than many have expected. "Right now, quantum computing looks
very difficult," he admits.
"There's no getting around that. But it's very difficult to say
what will happen five years from now."
Want more info about Grover's work? Check out Science News Online for
June 14,
1997 and August 31,
1996.
