Skip to content

Quantum Mechanics Helps in Searching for a Needle in a Haystack

Lov K. Grover

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.

  1. Quantum supremacy using a programmable superconducting processor2019
  2. Quantum theory, the Church–Turing principle and the universal quantum computer1985
  3. Scheme for reducing decoherence in quantum computer memory1995
  4. Wave function of the Universe1983

Metadata from OpenAlex (CC0). Citations are generated from the published record.