115
Part Three · B · Algorithms

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 ∣s⟩|s\rangle over NN items, with one marked item ∣w⟩|w\rangle. Everything happens in the plane spanned by ∣w⟩|w\rangle and the unmarked states. The oracle flips the sign of ∣w⟩|w\rangle: a reflection. The diffusion step, 2∣s⟩⟨s∣−12|s\rangle\langle s| - \mathbb 1, reflects about ∣s⟩|s\rangle. Two reflections make a rotation by 2θ2\theta, where sin⁡θ=1/N\sin\theta = 1/\sqrt N. Each round turns the state 2θ2\theta closer to ∣w⟩|w\rangle. Established

How many rounds

After kk rounds the success probability is sin⁡2((2k+1)θ)\sin^2((2k+1)\theta), so stop at about π4N\frac\pi4\sqrt N. Set log⁡2N=\log_2N = 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 N=220N = 2^{20}, 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 O(N/M)O(\sqrt{N/M}) 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 N\sqrt N 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 pp of any quantum subroutine to near 1 in O(1/p)O(1/\sqrt p) repetitions instead of O(1/p)O(1/p). 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 π4N\frac\pi4\sqrt N 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.

What happens if you run too many Grover rounds?tap
The state rotates past the target and the success probability drops.
Can Grover’s algorithm solve NP-complete problems efficiently?tap
No; the speedup is only quadratic, and that is provably optimal for unstructured search.
Why may a quadratic speedup not help in practice?tap
Error-corrected quantum steps are far slower than classical ones, so the break-even point is very large.

And one to work out. About how many Grover iterations for N=106N = 10^6, using π4N\frac\pi4\sqrt N?

k ≈

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.

Next · Chapter 116
Amplitude estimation and quantum Monte Carlo

Quadratically fewer samples for any Monte Carlo estimate, on paper.

Turn the page