Quantum Mechanics Helps in Searching for a Needle in a Haystack
Physical Review Letters · 1997 · 4,430 citationsOpen access
No retraction on record in OpenAlex.Check Crossref now
Cite this paper
Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79(2), 325–328. https://doi.org/10.1103/physrevlett.79.325
In text: (Grover, 1997)
Ask a question about this research
One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.
Abstract
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 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 $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 randomly. As a result, the desired phone number can be obtained in only $O(\sqrt{N})$ accesses to the database.
Related papers
Metadata from OpenAlex (CC0). Citations are generated from the published record.