Quantum quirks quicken thorny searches.

It's tough enough to find a specific entry in a crazy phone book in which names are listed randomly rather than alphabetically. It's even harder when you don't know the complete name and have only fragments of an address or a phone number.

Researchers have shown theoretically that quantum physics offers powerful methods for speeding up database searches (SN: 8/31/96, p. 143). A novel extension of these methods now promises a quick way of identifying items in a large, unsorted database that satisfy the terms of a somewhat vague inquiry.

Lov K. Grover of Lucent Technologies' Bell Labs in Murray Hill, N.J., described his enhanced quantum-search algorithm last week in Portland, Ore., at the Association for Computing Machinery's symposium on theory of computing.

An ordinary computer stores and processes information in units called bits, typically represented by electric voltages that are either high or low and given values of 1 or 0. In a quantum computer, the unit of information is a quantum bit, or a qubit, represented by the state of a quantum particle, such as an atom or a photon. For example, a horizontally polarized photon could signify 0 and a vertically polarized photon could signify 1.

Quantum mechanics, however, also allows a mixture, or superposition, of these two states--similar to the simultaneous sounding of two different frequencies by a bell. In principle, it's possible to take advantage of such combined states to perform certain computations more quickly on a quantum computer than on a conventional computer (SN: 1/14/95, p. 30).

In 1996, Grover showed theoretically how to represent all items in a database as a superposition of quantum states. He then demonstrated that a sequence of appropriate quantum operations, each of which slightly alters the system, would amplify the particular quantum state corresponding to the target of a search. In effect, the target state would become more and more likely to be measured in the final step of the quantum computation.

Extending this idea, Grover developed a quantum algorithm that leads not just to a single solution but to multiple acceptable solutions. "This yields new applications," Grover says.

For example, it can reduce the number of steps required to statistically sample a population according to an arbitrary probability distribution. The same method may narrow down a search when complete information about the target isn't available.