Wikinventia — Atlas of discoveries and inventions · Global Age

Grover's algorithm — Lov Grover

1996 AD · Transmission: Global
ComputingPhysicsMethodNorth American

In 1996 Lov Grover, at Bell Labs, presents at STOC a quantum algorithm searching an unstructured database of N elements in O(√N) operations versus O(N) classically — a quadratic, provably optimal speedup for unstructured search. Its amplitude-amplification mechanism has direct implications for symmetric cryptography, halving the effective bit-security of algorithms like AES and motivating doubled key lengths in post-quantum standards.

InstitutionBell Labs
Historical regionUSA
Primary sourceGrover, L.K. — "A fast quantum mechanical algorithm for database search" (1996). DOI: 10.1145/237814.237866
Secondary sourceBennett, C.H. et al. — "Strengths and Weaknesses of Quantum Computing" (1997)
Original languageEnglish
View this entry in the interactive atlas → View in graph →