Search in the Blink of a Photon

Quantum computers are a long way off, but scientists are already busy dreaming up software for them. One such algorithm, for example, could factor a thousand-digit number in about half an hour--a feat that would take even the fastest existing supercomputer about 10 billion times the age of the universe. Now a new quantum algorithm, to be reported in the 16 March issue of Physical Review Letters, could dramatically speed up chores like searching through reams of data.

To solve a task involving multiple searches and comparisons--say, scheduling students and teachers into appropriate time slots for classes--a standard computer must sequentially grind through each possible combination. The computer works out a preliminary scenario, then counts how many people have conflicts. It moves one person around, checks whether that resolves the conflict, and repeats the process until it hits upon the perfect solution--one with no conflicts. Each possible schedule is represented by a string of ones and zeros, and the computer can only deal with one schedule at a time.

A quantum computer, however, could do better. Since each "bit" of information can have more than one state at a time--represented by the quantum characteristics of a particle like an electron or photon--a string of quantum bits can hold all possible schedules at the same time. Tad Hogg of the Xerox Palo Alto Research Center in California developed a quantum algorithm that simultaneously sets up all the schedules. To extract the answer, one would simply measure the quantum state of the particles. This forces the system to choose one of the possible configurations--in this analogy, one schedule. Each schedule has a calculable probability of being chosen, and Hogg's algorithm fixes the system so that the most likely schedule is the one with the fewest conflicts--the best answer.

The algorithm is the fastest quantum search yet developed, says Lov Grover, an electrical engineer at Lucent Technologies in Murray Hills, New Jersey. Even if quantum computers are years away from being built, he adds, studying quantum algorithms clarifies the nature of problems by probing their structures ever more deeply.