Quantum Mechanics Helps in Searching for a Needle in a Haystack

Quantum Mechanics Helps in Searching for a Needle in a Haystack

Lov K. Grover*

3C-404A Bell Labs, 600 Mountain Avenue, Murray Hill, New Jersey 07974

(Received 4 December 1996)

Quantum mechanics can speed up a range of search applications over unsorted data. For example,

imagine a phone directory containing N names arranged in completely random order. To find some-

one’s phone number with a probability of 50%, any classical algorithm (whether deterministic or proba-

bilistic) will need to access the database a minimum of 0.5N 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 ran-

domly. As a result, the desired phone number can be obtained in only O(N^1/2) accesses to the database.