Tutorial 9 of 12 · Simulated in your browser
Grover’s search
Find a marked item among N by steering amplitude towards it, in about √N steps. Step through the iterations and watch the answer grow.
- Amplitude bars
- Shots
The search
Marked: 100110 (bit strings, qubit 0 on the left). A classical search of 64 unsorted items checks about 32 on average with one marked item; the best Grover count here, for 1 marked, is 6 iterations.
Amplitudes
Bar height is the amplitude, up for positive and down for negative; colour is its phase (green positive, magenta negative). All the unmarked amplitudes are equal at every step, so one bar stands for them all.
Success probability
1.6%
Simulated, after 0 iterations. The formula sin²((2k + 1)θ) gives 1.6%.
Rotation diagram
The state lives in a plane: horizontal is “all unmarked, equally”, vertical is “all marked, equally”. Each iteration turns it by 2θ = 14.4° towards the answer; the oracle alone mirrors it across the horizontal axis.
Read it out
Shots are of the state shown above. Step to the best count first, then read it out: the marked bars should hold nearly all of the shots. Dashed outlines are the exact chances.
The problem: a list of N items with no order, one of which is marked, and the only way to find it is to ask about items one at a time. A classical search checks about half the list on average before it finds a single marked item. Grover’s algorithm finds it with a number of steps that grows like the square root of N, instead of N.
It starts with all N items in an equal superposition, every amplitude 1/√N. Each iteration is two reflections. The oracle flips the sign of the marked amplitude, which the bars show as a bar dropping below the line. The diffusion step then reflects every amplitude about their mean, which lifts the marked one further and lowers all the others a little. The sign flip is what makes the mean slip below the unmarked amplitudes, so the reflection pushes the marked bar up.
There is a tidy geometry underneath. The whole state stays in a plane spanned by the marked states and the unmarked ones, and each iteration turns it by an angle 2θ towards the marked direction, where sin θ = √(M/N) for M marked items. After k iterations the chance of reading a marked item is sin²((2k + 1)θ). The rotation diagram draws that turn, and the plot puts the simulated points on the formula’s curve.
How many iterations? The best count is the whole number ⌊π/(4θ)⌋, about (π/4)√N for one marked item, and then the chance of failure is at most M/N. Do not keep going: the state turns past the answer and the chance falls again, then rises again, in a cycle. For N = 4 with one marked item, θ is 30 degrees, and one iteration lands exactly on 1. Step the slider past the best count and watch the marked bar shrink.
What is computed here and what is the formula. The dots come from running the actual circuit, an oracle and a diffusion step repeated, on the full list of amplitudes in your browser, and the curve is the formula. The page’s check compares the two for every N from 4 to 1,024 and for one, two or three marked items. The bars show all N items up to 16; beyond that they show the marked items and one bar for every other item, because all the unmarked amplitudes are equal at every step.
Keep it in proportion: this is a square-root speed-up, not an exponential one, and it counts questions to the oracle. Grover’s own abstract notes that the speed-up is within a small constant factor of the best possible for this problem. Nothing on this page says how fast any real machine would run it.
Qubit order: bit strings are written with qubit 0 on the left, as in Nielsen and Chuang’s book. (Qiskit puts it on the right.)
Sources
Grover 1996 A fast quantum mechanical algorithm for database search. Lov K. Grover, arXiv quant-ph/9605043, 29 May 1996 (STOC ’96).
- Abstract: O(√N) steps for database search
- Abstract: within a small constant factor of the fastest possible
IBM, Quantum Algorithms Fundamentals of Quantum Algorithms (IBM Quantum Learning). IBM. Live course: Deutsch–Jozsa, Simon, phase estimation, Shor and Grover.
- The Grover’s algorithm lesson
Quantum Country, search How the quantum search algorithm works. Andy Matuschak and Michael Nielsen. Live essay; no date shown on the page.
- The rotation picture, of which the two reflections are the steps
- The rotation picture
Boyer et al. 1996 Tight bounds on quantum searching. M. Boyer, G. Brassard, P. Høyer and A. Tapp, arXiv quant-ph/9605034, 23 May 1996.
- Section 3: sin²θ = M/N and success probability sin²((2k+1)θ)
- Section 3: the iteration count ⌊π/(4θ)⌋ and the failure bound M/N
Everything here is paraphrased from the sources, not quoted, and every figure that is not plain arithmetic is attributed. The simulator is this site’s own and is tested against the formulas on the page. Where a source is silent the page says so.