Computing, IT & AI
Grover's quantum search algorithm
1996 CELov Grover (Bell Labs)A fast quantum mechanical algorithm for database search (STOC 1996)Diaspora (work abroad)
1996
A quantum algorithm that searches N unsorted items in about the square root of N steps.
- Dated
- 1996
- As scholars put it
- 1996 CE
- Originator
- Lov Grover (Bell Labs)
- Source text
- A fast quantum mechanical algorithm for database search (STOC 1996)
- Region
- Diaspora (work abroad)
- Discipline
- Computing, IT & AI
- Evidence
- Documented
- Confidence
- High
- Verification
- Verified-web
Background
Lov Grover, an IIT Delhi graduate working at Bell Labs, published this algorithm in 1996. A classical search must check items one by one; Grover's algorithm amplifies the probability of the right answer to find it in about √N steps.
Significance
The second major quantum algorithm after Shor's, and provably optimal for unstructured search. It is a building block in many quantum algorithms and sets the key-length requirements of post-quantum cryptography.
Path to modern innovation
Run on real quantum hardware; the reason symmetric keys are being doubled in length.
Global impact
- Amplitude amplification, a general quantum technique.
- Security guidance for symmetric cryptography in a quantum future.
Primary sources
Further reading
Related
Corrections and additional sources: edit IND-399 on GitHub.