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.

[ Lov Grover ]

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."