Abstract
Quantum mechanics can speed up a range of search applications over unsorted data. For example, imagine a phone directory containing names arranged in completely random order. To find someone's phone number with a probability of 50%, any classical algorithm (whether deterministic or probabilistic) will need to access the database a minimum of times. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained in only accesses to the database.
- Received 4 December 1996
DOI:https://doi.org/10.1103/PhysRevLett.79.325
©1997 American Physical Society