MilestoneTheory & algorithmsConfirmed
Lov Grover finds a quantum algorithm for faster unstructured search
May 1996
Lov Grover of Bell Labs presents a quantum algorithm that finds a marked entry in an unsorted list of N items in roughly the square root of N steps, while a classical search must check about N/2 entries to have even odds. He presented it at the STOC conference in May 1996.
Why it matters
It showed that quantum computers can speed up even generic search, though only quadratically, a much smaller gain than Shor's exponential speedup for factoring.
Lov Grover · Bell Labs
Related
Sources (3)
-
arXiv (Lov K. Grover)
A fast quantum mechanical algorithm for database search
“Imagine a phone directory containing N names arranged in completely random order. In order to find someone's phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names. 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)) steps.”
-
arXiv (Peter W. Shor)
The Early Days of Quantum Computation
“And Lov Grover, at Bell Labs, discovered a quantum search algorithm that does quadratically better than the best classical search algorithm”
-
Physical Review Letters
Quantum Mechanics Helps in Searching for a Needle in a Haystack
“Quantum mechanics can speed up a range of search applications over unsorted data.”
Each quote above was checked automatically against the original page. Added Oct 15, 2026. Spotted an error? Tell us and we will review it.