How can a quantum computer find the one marked item among N in about √N steps, and why can nothing do better?
Every algorithm on this page so far has been a part or a special case. These two are the ones the world has heard of, and they are the two the rest of this site leans on: Grover's quadratic speed-up for unstructured search, which sets how much a symmetric key must grow, and Shor's exponential one for factoring, which is why public-key cryptography is being replaced. Each topic has a problem set with worked solutions, and a notebook that runs the whole thing with nothing but NumPy.
You are given N doors and a test that, for any one door, says yes or no. Exactly one door says yes. With no structure to exploit, a classical search has to open doors: on average about half of them, in the worst case all N. Grover's algorithm (Grover, 1996) finds the door in about (π/4)√N applications of the test, and it never needs to look inside the test: it only calls it, as a black box, which is what topic 08 calls an oracle.
What one iteration does. Start with all N doors in equal superposition, each with amplitude 1/√N. The oracle flips the sign of the marked door's amplitude, using the phase kickback of topic 08: nothing about the probabilities has changed yet, because a sign is invisible to a measurement. Then comes the diffusion step, inversion about the average: every amplitude a becomes 2ā − a, where ā is the average amplitude. The marked door, now below the average, is thrown far above it; every other door is nudged down a little. Each iteration, the marked door's amplitude grows by roughly 2/√N, so about √N of them are enough.
A case you can do by hand. With N = 4 doors all four amplitudes are ½. The oracle makes them (½, ½, ½, −½), whose average is ¼. Inversion about the average gives 2·¼ − ½ = 0 for each unmarked door and 2·¼ + ½ = 1 for the marked one: after one iteration the answer is certain. With N = 8 one iteration is not enough: the amplitudes go from 0.3536 to 0.8839 for the marked door and 0.1768 for each of the others, a probability of 25/32 = 78% for the marked one. A second iteration takes it to 121/128 = 94.5%.
It is not a speed-up you can overshoot. The rotation does not stop at the target: keep iterating past the peak and the marked door's probability falls again. For N = 4 it runs ¼, 1, ¼, ¼, 1, ¼, ¼: a second iteration undoes the first. For N = 64 the best number is 6 iterations (99.66%); nine leave 47.5 percent and twelve leave 0.007 percent. This is the lesson of Grover's Escape: you have to know when to stop.
What this does not mean. It is a quadratic speed-up, √N against N, not an exponential one; the oracle has to be built as a circuit, and its cost is part of the bill; and it only helps when there is nothing better than trying doors. A search over a structured problem (sorted data, an index, an algebraic structure) usually has a classical shortcut that beats √N altogether.
The plane. Let w be the marked item, |s⟩ = N−1/2 Σx |x⟩ the uniform state, and |s′⟩ = (N−1)−1/2 Σx≠w |x⟩ the uniform state over the unmarked items. Then |s⟩ = sin θ |w⟩ + cos θ |s′⟩ with sin θ = 1/√N. The whole algorithm lives in the plane spanned by |w⟩ and |s′⟩.
The two operators. The oracle is O = I − 2|w⟩⟨w|: a reflection in the |s′⟩ axis. The diffusion operator is D = 2|s⟩⟨s| − I: a reflection about |s⟩, with matrix entries Dxy = 2/N − δxy (for N = 4 that is −½ on the diagonal and +½ everywhere else). Both are unitary and square to the identity. D is built from H⊗n and a reflection about |0…0⟩: D = H⊗n(2|0⟩⟨0| − I)H⊗n, and 2|0⟩⟨0| − I is a phase flip on one basis state, a multi-controlled Z conjugated by X gates. For two qubits that is the circuit H·H, X·X, CZ, X·X, H·H, which equals −D (a global sign, unobservable); with CZ as the oracle for |11⟩, one iteration lands on |11⟩ with probability 1.
The rotation. The product G = DO of two reflections is a rotation by 2θ, twice the angle between their mirrors, so
Gk|s⟩ = sin((2k+1)θ) |w⟩ + cos((2k+1)θ) |s′⟩, Pk = sin²((2k+1)θ)
The probability is largest when (2k+1)θ is as close to π/2 as an integer k allows, so the number of iterations is k* = ⌊π/(4θ)⌋ ≈ (π/4)√N. Because (2k*+1)θ lies within θ of π/2, the failure probability after k* iterations is at most sin²θ = 1/N. Exact values: N = 4, k* = 1, P = 1; N = 8, k* = 2, P = 121/128 = 0.9453125 (from sin 5θ = s(5 − 20s² + 16s⁴) with s² = 1/8); N = 16, k* = 3, P = 0.9613; N = 64, k* = 6, P = 0.9966; N = 1,024, k* = 25, P = 0.9995; and N = 1,000,000, k* = 785, P > 0.999999. All of these, the closed form against a direct state-vector simulation for N up to 1,024, and the bound 1/N, are recomputed in the closed form against an explicit simulation of the oracle and diffusion step, for N = 4 to 1,024, one and several marked items.
Several marked items. With M marked items sin θ = √(M/N), and k* ≈ (π/4)√(N/M). When M = N/4, θ = π/6 and a single iteration is exact: for N = 16 with four marked items the first iteration gives probability exactly 1. If M is not known, Boyer, Brassard, Høyer and Tapp (Fortschr. Phys. 46, 493, 1998, arXiv quant-ph/9605034) give an algorithm that finds a marked item in expected O(√(N/M)) oracle calls without knowing M.
Nothing does better. Bennett, Bernstein, Brassard and Vazirani (SIAM J. Comput. 26, 1510, 1997, arXiv quant-ph/9701001) proved that any quantum algorithm that finds the marked item must call the oracle Ω(√N) times, so the speed-up cannot be improved to anything better than quadratic in the black-box setting. Zalka (Phys. Rev. A 60, 2746, 1999, arXiv quant-ph/9711070) tightened this to a matching bound: Grover's algorithm is optimal for every success probability, about (π/4)√N queries for near-certainty. Grover's original paper is A fast quantum mechanical algorithm for database search, Proc. 28th ACM STOC (1996), 212–219, arXiv quant-ph/9605043.
The count. For N = 1,000,000 a classical search without repeats takes 500,000.5 tests on average; Grover takes 785 iterations: about a 637-fold reduction in oracle calls. The ratio grows as √N, so it is modest at small N and large at large N, but each Grover iteration also costs a diffusion step on top of the oracle.
Symmetric keys, and why the speed-up is smaller in practice than on paper A brute-force search for a 128-bit key is a search over N = 2128 possibilities, and the test is a full encryption. Grover needs (π/4)·264 = 1.45 × 1019 serial oracle calls, each a whole AES circuit. If one call took a microsecond (a generous assumption for an error-corrected machine) that is about 459,000 years. The iterations cannot simply be split between machines for a linear gain: running p machines, each searching N/p keys, takes (π/4)√(N/p) calls each, so a p-fold increase in machines buys only a √p-fold saving, and finishing in one year at a microsecond per call would need about 2.1 × 1011 machines. That is why the standard conclusion is that a symmetric key length doubles in a quantum world, not that symmetric encryption breaks, and why Grover is far less of a threat than Shor's algorithm. Babbush and colleagues (arXiv 2011.04149) make the general point: once the overheads of error correction are counted, quadratic speed-ups are marginal on early fault-tolerant machines.
Grover's trick, amplifying the part of a state you care about by repeated reflections, is called amplitude amplification (Brassard, Høyer, Mosca and Tapp, AMS Contemporary Mathematics 305, 53, 2002, arXiv quant-ph/0005055) and is a subroutine in many other algorithms, including quantum counting and the search step inside several quantum-walk and optimisation methods.
Six problems. Every answer below was recomputed by a program written separately from this page; try each before opening the solution. A notebook that runs all of this with nothing but NumPy is at grover.ipynb (open it in Jupyter, VS Code or Colab).
Problem 1. N = 8, one marked item. How many iterations should you run, and with what probability do you then find it?
sin θ = 1/√8, so θ = 0.3614 radians and π/(4θ) = 2.17, giving k* = 2. The probability is sin²(5θ) = 121/128 = 0.9453. (One iteration gives sin²(3θ) = 25/32 = 0.78125; a third gives sin²(7θ) = 0.33, which is worse.)
Problem 2. N = 16 and four items are marked. Show that a single iteration finds a marked item with certainty.
sin θ = √(4/16) = ½, so θ = π/6. After one iteration the angle is 3θ = π/2, so sin²(π/2) = 1. The state has been rotated all the way onto the marked items.
Problem 3. N = 1,000,000. How many iterations, and how many fewer oracle calls than the classical average of a search without repeats?
θ = arcsin(10−3) ≈ 0.001, so π/(4θ) = 785.4 and k* = 785, with success probability above 0.999999. The classical average is (N + 1)/2 = 500,000.5 calls, so Grover uses about 500,000.5/785 = 637 times fewer.
Problem 4. For N = 64, what is the probability of success after nine iterations, and after twelve? What does N = 4 do if you run two iterations?
θ = arcsin(1/8) = 0.12533. After nine iterations sin²(19θ) = 0.475; after twelve sin²(25θ) = 0.00007, which is 0.007 percent. For N = 4, θ = π/6 and two iterations give sin²(5π/6) = ¼: back to the starting probability, which is the same as guessing.
Problem 5. Write the diffusion matrix for N = 4 and apply it to the state after the oracle, (½, ½, ½, −½). Check that you get (0, 0, 0, 1).
Dxy = 2/N − δxy, so D has −½ on the diagonal and +½ elsewhere. The first row gives −½·½ + ½·½ + ½·½ + ½·(−½) = 0, and likewise for the second and third rows. The fourth row gives ½·½ + ½·½ + ½·½ − ½·(−½) = 1. This is inversion about the average: the average is ¼, and 2·¼ − (−½) = 1.
Problem 6. How many serial oracle calls does Grover need against a 128-bit key? If a call takes one microsecond, how long is that, and how many machines working in parallel would finish in a year?
(π/4)·264 = 1.45 × 1019 calls, which at one microsecond each is about 459,000 years. With p machines each takes (π/4)√(2128/p) calls, so a year (3.156 × 1013 microseconds) needs p = (π/4)²·2128/(3.156 × 1013)² ≈ 2.1 × 1011 machines. The one-microsecond figure is an assumption, and a generous one; slower calls make every number larger.
Check yourself
A corridor has N = 64 doors and one exit. You run Grover's algorithm for 6 iterations and then keep going to 12. What happens to the probability of finding the exit?
Each iteration turns the state by 2θ in a plane, with sin θ = 1/8, so the probability is sin²((2k+1)θ). It peaks at k = 6 (99.66 percent) and then falls: 47.5 percent at k = 9 and 0.007 percent at k = 12. The algorithm needs you to know when to stop.
The tempting wrong answers.