Grover's Search Algorithm
Grover's Search Algorithm
Grover's algorithm finds a marked item among N items with about (π/4)√(N/M) queries, by amplitude amplificationAmplitude Amplification: Amplitude amplification is a generalisation of Grover's algorithm: two successive reflections rotate the state towards the "good" subspace by an angle 2θ per iteration,…: an oracle flips the sign of the marked items, then a diffusion operator reflects the amplitudes about their mean.
We start with the uniform superposition $|s\rangle=H^{\otimes n}|0\rangle$. Each iteration consists of:
- The oracle $O=I-2\sum_{m}|m\rangle\langle m|$: flips the sign of the marked items.
- Diffusion $D=2|s\rangle\langle s|-I$: a reflection about the mean.
If we define $\sin\theta=\sqrt{M/N}$, the success probability after $k$ iterations is $\sin^2((2k+1)\theta)$, and the optimal number of iterations is $k^*=\lfloor\frac{\pi}{4\theta}\rfloor\approx\frac{\pi}{4}\sqrt{N/M}$. Beyond $k^*$ the rotation overshoots the target and the probability decreases. So iterating "more to be safe" is wrong.
Theoretical complexity versus simulation: the quadratic speed-up in the number of queries is real and proven ($\Omega(\sqrt N)$ lower bound). But simulating Grover on a classical computer costs $O(2^n)$ per gate, so the simulator in your browser is slower than ordinary linear search. The simulation proves the correctness of the probabilities, not the speed. Building the oracle for a real problem may also swallow the benefit in practice.
Mathematical formulation
Worked example
In the "Grover" experiment, choose 4 qubits (N = 16) and target 11: the optimal number of iterations is 3, with a success probability of about 0.961. Set the iterations to 6 and the probability drops sharply, as the "theory versus simulation" curve shows.
Try it yourself: Grover's Algorithm
Test your understanding
The quiz needs JavaScript.
References
- Lov K. Grover (1996). A fast quantum mechanical algorithm for database search. Proc. 28th ACM STOC, pp. 212–219 doi:10.1145/237814.237866
- Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp (1998). Tight Bounds on Quantum Searching. Fortschritte der Physik 46(4-5):493–505 doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
- Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
