Quantum Computing
Lov Grover
Found the quantum search algorithm.
born 1961, India · India, working in the United States
Who they were
An Indian-born computer scientist at Bell Labs.
What they found or built
In 1996 he showed that a quantum computer can find one marked item among N unsorted items in about the square root of N steps, where a classical computer needs about N/2. The method starts with all items in equal superposition and then repeatedly flips the sign of the right answer and reflects all amplitudes about their average, which nudges more and more weight onto the target.
Why it mattered
Grover's speed-up is quadratic, not exponential, and later work proved that no quantum algorithm can do better for this problem. It is a lasting and honest lesson: quantum computers are not magic search engines, and their advantages depend on the structure of the problem. The algorithm is nonetheless used as a building block in many others.
Equations and key ideas
- Amplitude amplification
- Quadratic speed-up