Grover's search, amplitude amplification, and its optimality
To find the one marked item among a million, checking items one by one takes half a million looks on average. Lov Grover showed in 1996 that a quantum computer needs about 800. That is a real, provable speedup, and it applies to almost any search problem. It is also only quadratic, not exponential, and on realistic error-corrected hardware, where every quantum step is slow, the crossover point where it actually wins can be very far away.
On the plate: Grover’s algorithm as a rotation in a plane.
Two reflections make a rotation
Start in the uniform superposition over items, with one marked item . Everything happens in the plane spanned by and the unmarked states. The oracle flips the sign of : a reflection. The diffusion step, , reflects about . Two reflections make a rotation by , where . Each round turns the state closer to . Established
How many rounds
After rounds the success probability is , so stop at about . Set 6 and run 6 rounds. Going past the optimum over-rotates and the probability falls again: unlike classical search, more work can make things worse. For , 804 rounds give success probability 0.9999998. If the number of marked items is unknown, randomly chosen iteration counts (Boyer, Brassard, Høyer and Tapp, 1998) still find one in rounds.
No better is possible
Charles Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani proved in 1997, by a “hybrid argument” that tracks how much each query can move the state, that any quantum algorithm needs at least about queries for unstructured search. Christof Zalka showed in 1999 that Grover’s algorithm is exactly optimal. So quantum computers cannot solve NP-complete problems by brute-force search in polynomial time. The general version, amplitude amplification, boosts the success probability of any quantum subroutine to near 1 in repetitions instead of . Established
When does it pay?
A quadratic speedup has to overcome a large constant-factor slowdown. An error-corrected logical operation, including all the error-correction work, takes microseconds or more, against nanoseconds for a classical one, and the oracle itself may need thousands of logical gates. Ryan Babbush and colleagues estimated in 2021 that, for plausible early fault-tolerant hardware, quadratic speedups for optimization problems would need running times of days to break even, and that problems with only quadratic advantage are unlikely to be the first useful applications. Larger-than-quadratic speedups are what matter. Debated, since it depends on future hardware speeds.
What you now have
Grover’s algorithm as two reflections and a rotation, the iteration count and over-rotation, unknown numbers of solutions, the BBBV lower bound and Zalka’s optimality, amplitude amplification, and the realistic economics of quadratic speedups.
· · ·
Three questions to carry with you.
And one to work out. About how many Grover iterations for , using ?
Sources: L. K. Grover, Proc. 28th ACM STOC, 212 (1996). C. H. Bennett, E. Bernstein, G. Brassard and U. Vazirani, SIAM J. Comput. 26, 1510 (1997). C. Zalka, Phys. Rev. A 60, 2746 (1999). M. Boyer, G. Brassard, P. Høyer and A. Tapp, Fortsch. Phys. 46, 493 (1998). G. Brassard, P. Høyer, M. Mosca and A. Tapp, Contemp. Math. 305, 53 (2002). R. Babbush et al., PRX Quantum 2, 010103 (2021). Checked by code: N = 2²⁰ → 804 iterations, P = 0.99999976; N = 10⁶ → 785.