Simple Algorithm
Quantum Computing · Excited State · 24 min

Grover's Search & Amplitude Amplification

Finding a needle in √N steps by rotating amplitude.

Searching NN unsorted items classically takes about NN looks. Grover's algorithm takes about π4N\frac{\pi}{4}\sqrt N, by alternating two reflections that together rotate the state toward the answer. The same rotation, amplitude amplification, speeds up a huge range of other algorithms.

What you’ll learn

  • Write the oracle and the diffusion as reflections and show that diffusion is inversion about the mean.
  • Derive the success probability sin⁡2((2k+1)θ)\sin^2((2k+1)\theta) with sin⁡θ=M/N\sin\theta=\sqrt{M/N} and the optimal number of iterations.
  • Build the diffusion from Hadamards, XX gates and a multi-controlled ZZ, and run the 2-qubit circuit.
  • Handle several or unknown numbers of marked items, and generalize to amplitude amplification.
  • Explain the limits: quadratic optimality, oracle cost, data loading and overheads.

Search as a query problem

Let f:{0,…,N−1}→{0,1}f:\{0,\dots,N-1\}\to\{0,1\} with N=2nN=2^n, and call xx marked if f(x)=1f(x)=1. Suppose MM items are marked. With no structure to exploit, a classical algorithm needs Θ(N/M)\Theta(N/M) queries to find one; for M=1M=1, about N/2N/2 on average.

Quantumly, one query gives the phase oracle through phase kickback (see Oracles & Phase Kickback: Deutsch–Jozsa), and the uniform superposition is one layer of Hadamards away:

Of∣x⟩=(−1)f(x)∣x⟩,∣s⟩=H⊗n∣0n⟩=1N∑x∣x⟩.O_f\ket{x}=(-1)^{f(x)}\ket{x},\qquad\ket{s}=H^{\otimes n}\ket{0^n}=\frac{1}{\sqrt N}\sum_{x}\ket{x}.
Of=I−2 Πgood,D=2∣s⟩ ⁣⟨s∣−I,G=D OfO_f=\id-2\,\Pi_{\text{good}},\qquad D=2\dyad{s}-\id,\qquad G=D\,O_f
Πgood=∑f(x)=1∣x⟩ ⁣⟨x∣\Pi_{\text{good}}=\sum_{f(x)=1}\dyad{x}. The Grover iterate GG applies the oracle, then the diffusion.
DerivationDiffusion is inversion about the mean
  1. ∣ψ⟩=∑xax∣x⟩,⟨s∣ψ⟩=1N∑xax=N aˉ\ket{\psi}=\sum_x a_x\ket{x},\qquad\braket{s|\psi}=\frac{1}{\sqrt N}\sum_x a_x=\sqrt N\,\bar a

    Write aˉ\bar a for the mean amplitude.

  2. 2∣s⟩⟨s∣ψ⟩=2N aˉ⋅1N∑x∣x⟩=∑x2aˉ ∣x⟩2\ket{s}\braket{s|\psi}=2\sqrt N\,\bar a\cdot\frac{1}{\sqrt N}\sum_x\ket{x}=\sum_x2\bar a\,\ket{x}

    Projecting onto ∣s⟩\ket{s} replaces every amplitude by the mean.

  3. D∣ψ⟩=∑x(2aˉ−ax)∣x⟩D\ket{\psi}=\sum_x\big(2\bar a-a_x\big)\ket{x}

    Each amplitude is reflected about the mean: ax↦aˉ−(ax−aˉ)a_x\mapsto\bar a-(a_x-\bar a). The marked amplitude, just negated by the oracle, sits far below the mean, so it lands far above it.

Two reflections make a rotation

Everything happens in a plane. Define the normalized good and bad states

∣w⟩=1M∑f(x)=1∣x⟩,∣w⊥⟩=1N−M∑f(x)=0∣x⟩.\ket{w}=\frac{1}{\sqrt M}\sum_{f(x)=1}\ket{x},\qquad\ket{w^\perp}=\frac{1}{\sqrt{N-M}}\sum_{f(x)=0}\ket{x}.

Then ∣s⟩=sin⁡θ ∣w⟩+cos⁡θ ∣w⊥⟩\ket{s}=\sin\theta\,\ket{w}+\cos\theta\,\ket{w^\perp} with sin⁡θ=M/N\sin\theta=\sqrt{M/N}, and both OfO_f and DD map the plane span{∣w⟩,∣w⊥⟩}\mathrm{span}\{\ket{w},\ket{w^\perp}\} to itself.

DerivationThe Grover rotation
  1. Of(α∣w⟩+β∣w⊥⟩)=−α∣w⟩+β∣w⊥⟩O_f\big(\alpha\ket{w}+\beta\ket{w^\perp}\big)=-\alpha\ket{w}+\beta\ket{w^\perp}

    In the plane, the oracle is the reflection about the axis ∣w⊥⟩\ket{w^\perp}.

  2. D=2∣s⟩ ⁣⟨s∣−ID=2\dyad{s}-\id

    The diffusion is the reflection about the axis ∣s⟩\ket{s}, which makes the angle θ\theta with ∣w⊥⟩\ket{w^\perp}.

  3. G=D Of=rotation by 2θ  from ∣w⊥⟩ toward ∣w⟩G=D\,O_f=\text{rotation by }2\theta\ \text{ from }\ket{w^\perp}\text{ toward }\ket{w}

    Two reflections whose axes meet at angle θ\theta compose to a rotation by 2θ2\theta. The start state sits at angle θ\theta; each iteration adds 2θ2\theta.

  4. Gk∣s⟩=sin⁡((2k+1)θ)∣w⟩+cos⁡((2k+1)θ)∣w⊥⟩G^k\ket{s}=\sin\big((2k+1)\theta\big)\ket{w}+\cos\big((2k+1)\theta\big)\ket{w^\perp}

    After kk iterations the angle is (2k+1)θ(2k+1)\theta.

  5. Pk=sin⁡2((2k+1)θ),sin⁡θ=M/NP_k=\sin^2\big((2k+1)\theta\big),\qquad\sin\theta=\sqrt{M/N}

    Measuring then yields a marked item with probability PkP_k (uniformly random among the marked ones).

Choose kk so that (2k+1)θ≈π/2(2k+1)\theta\approx\pi/2:

k∗=⌊π4θ⌋ ≈ π4NM(M≪N).k^\ast=\Big\lfloor\frac{\pi}{4\theta}\Big\rfloor\ \approx\ \frac{\pi}{4}\sqrt{\frac NM}\quad(M\ll N).

Then ∣(2k∗+1)θ−π2∣≤θ\abs{(2k^\ast+1)\theta-\frac\pi2}\le\theta, so Pk∗≥cos⁡2θ=1−M/NP_{k^\ast}\ge\cos^2\theta=1-M/N. Overshooting is costly: PkP_k is periodic in kk and returns near zero after about 2k∗2k^\ast iterations.

Predict before you look

N=1024N=1024 items, one of them marked. What is k∗=⌊π/(4θ)⌋k^\ast=\lfloor\pi/(4\theta)\rfloor?

Show the answer

25 iterations

θ=arcsin⁡(1/32)≈0.03126\theta=\arcsin(1/32)\approx0.03126, so π/(4θ)≈25.13\pi/(4\theta)\approx25.13 and k∗=25k^\ast=25, with success probability sin⁡2(51θ)≈0.9995\sin^2(51\theta)\approx0.9995. Classical search needs about 512512 queries on average.

The circuit

The diffusion is cheap to build. Since ∣s⟩=H⊗n∣0n⟩\ket{s}=H^{\otimes n}\ket{0^n},

D=H⊗n(2∣0n⟩ ⁣⟨0n∣−I)H⊗n,D=H^{\otimes n}\big(2\dyad{0^n}-\id\big)H^{\otimes n},

and I−2∣0n⟩ ⁣⟨0n∣\id-2\dyad{0^n}, which flips only the sign of ∣0n⟩\ket{0^n}, equals X⊗n (Cn−1Z) X⊗nX^{\otimes n}\,\big(C^{n-1}Z\big)\,X^{\otimes n}: the multi-controlled ZZ flips the sign of ∣1⋯1⟩\ket{1\cdots1}, and the XX layers relabel it as ∣0⋯0⟩\ket{0\cdots0}. This implements −D-D; the global sign is invisible. A Cn−1ZC^{n-1}Z costs O(n)O(n) elementary gates with ancillas, so each iteration costs one query plus O(n)O(n) gates, and the diffusion never depends on which item is marked.

Check your understanding

Why does a single iteration succeed with certainty for N=4N=4, M=1M=1?

  1. Because sin⁡θ=12\sin\theta=\frac12, so θ=π/6\theta=\pi/6 and 3θ=π/23\theta=\pi/2 exactly
  2. Because two qubits decohere too slowly for errors to matter
  3. Because the diffusion operator is the identity for N=4N=4
  4. It doesn't: the success probability is 34\frac34
Show the answer

A. Because sin⁡θ=12\sin\theta=\frac12, so θ=π/6\theta=\pi/6 and 3θ=π/23\theta=\pi/2 exactly

P1=sin⁡2(3θ)P_1=\sin^2(3\theta) with sin⁡θ=1/4=12\sin\theta=1/\sqrt4=\frac12. Then θ=π/6\theta=\pi/6 and 3θ=π/23\theta=\pi/2: one rotation lands exactly on ∣w⟩\ket{w}. For larger NN the angle generally does not hit π/2\pi/2 exactly.

Many marked items, and amplitude amplification

With MM marked items the same analysis holds with sin⁡θ=M/N\sin\theta=\sqrt{M/N}: about π4N/M\frac{\pi}{4}\sqrt{N/M} iterations. But large MM holds a surprise.

Check your understanding

N=4N=4 with M=2M=2 marked items. What is the success probability after one Grover iteration?

  1. 100%100\%
  2. 50%50\%, unchanged
  3. 0%0\%
  4. 75%75\%
Show the answer

B. 50%50\%, unchanged

sin⁡θ=1/2\sin\theta=\sqrt{1/2}, so θ=π/4\theta=\pi/4 and P1=sin⁡2(3π/4)=12P_1=\sin^2(3\pi/4)=\frac12: the rotation by 2θ=π/22\theta=\pi/2 carries the state from 45°45° to 135°135°, the mirror-image angle. With M=3M=3 it is worse: θ=π/3\theta=\pi/3 and sin⁡2π=0\sin^2\pi=0. When M≥N/2M\ge N/2, just guess at random.

Unknown MM. Using the wrong count is dangerous. Run the M=1M=1 schedule when 44 items are marked and you rotate by about twice the right angle, ending near ∣w⊥⟩\ket{w^\perp}. Boyer, Brassard, Høyer and Tapp (1998) fix this with exponential search: pick kk uniformly from {0,…,m−1}\{0,\dots,m-1\}, run, check the result with one query, and on failure multiply mm by a constant λ∈(1,43)\lambda\in(1,\frac43). The expected number of queries is O(N/M)O(\sqrt{N/M}) without knowing MM. Alternatively, estimate MM first by quantum counting.

What Grover does, and does not, buy you

  • Optimal. No quantum algorithm searches an unstructured space with fewer than Ω(N/M)\Omega(\sqrt{N/M}) queries (Bennett, Bernstein, Brassard & Vazirani 1997; Boyer et al. 1998). Quadratic is the end of the road.
  • NP problems. Brute-force SAT over nn variables drops from about 2n2^n to 2n/22^{n/2} oracle calls, each a polynomial-size circuit evaluating the formula. Still exponential. Classical solvers exploit structure that plain Grover ignores, though quadratic speedups of some structured heuristics, such as backtracking, are known (Montanaro 2018).
  • Data loading. "Database search" is a metaphor. If the NN items are classical records, the oracle needs them in quantum-accessible memory (QRAM); without it, each query costs Ω(N)\Omega(N) gates and the speedup is gone.
  • Depth and overhead. The ∼N\sim\sqrt N iterations run one after another, and pp machines in parallel achieve only time N/p\sqrt{N/p}. On error-corrected hardware every logical gate is slow, and analyses suggest quadratic speedups pay off only at very large problem sizes (Babbush et al. 2021).

Key takeaways

  • The oracle and the diffusion are reflections; their product GG rotates by 2θ2\theta in span{∣w⟩,∣w⊥⟩}\mathrm{span}\{\ket{w},\ket{w^\perp}\}, with sin⁡θ=M/N\sin\theta=\sqrt{M/N}.
  • Pk=sin⁡2((2k+1)θ)P_k=\sin^2((2k+1)\theta); k∗=⌊π/(4θ)⌋≈π4N/Mk^\ast=\lfloor\pi/(4\theta)\rfloor\approx\frac\pi4\sqrt{N/M} gives success at least 1−M/N1-M/N, and overshooting hurts.
  • Diffusion is H⊗n(2∣0n⟩ ⁣⟨0n∣−I)H⊗nH^{\otimes n}(2\dyad{0^n}-\id)H^{\otimes n}: each iteration costs one query plus O(n)O(n) gates.
  • Unknown MM: use exponential search or counting. Any checkable algorithm with success probability aa can be amplified in O(1/a)O(1/\sqrt a) rounds.
  • The speedup is quadratic and optimal; its practical value depends on oracle cost, data loading and error-correction overhead.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

After the oracle, N=4N=4 amplitudes are (12,12,12,−12)(\frac12,\frac12,\frac12,-\frac12). What does D=2∣s⟩ ⁣⟨s∣−ID=2\dyad{s}-\id produce?

  1. (12,12,12,12)(\frac12,\frac12,\frac12,\frac12)
  2. (−12,−12,−12,12)(-\frac12,-\frac12,-\frac12,\frac12)
  3. (0,0,0,1)(0,0,0,1)
  4. (0,0,0,−1)(0,0,0,-1)
Show the answer

C. (0,0,0,1)(0,0,0,1)

The mean is aˉ=14\bar a=\frac14, and a↦2aˉ−aa\mapsto2\bar a-a sends 12↦0\frac12\mapsto0 and −12↦1-\frac12\mapsto1.

Question 2

You plan k≈π4Nk\approx\frac{\pi}{4}\sqrt N iterations for one marked item, but 44 items are actually marked (NN large). Roughly what success probability do you get?

  1. Close to 00
  2. Close to 11, as planned
  3. About 14\frac14
  4. About 12\frac12
Show the answer

A. Close to 00

Now sin⁡θ≈2/N\sin\theta\approx2/\sqrt N, twice as large, so after k≈π4Nk\approx\frac{\pi}{4}\sqrt N iterations the angle is (2k+1)θ≈π(2k+1)\theta\approx\pi: the state is back near ∣w⊥⟩\ket{w^\perp}. This is why unknown MM needs exponential search or counting.

Question 3

An algorithm A\mathcal A succeeds with probability a=1/100a=1/100, and success can be checked. With amplitude amplification, about how many rounds (each using A\mathcal A and A−1\mathcal A^{-1} once) are needed for near-certain success?

  1. On the order of 10001000
  2. On the order of 100100
  3. Just 11
  4. On the order of 1010
Show the answer

D. On the order of 1010

sin⁡θa=a=0.1\sin\theta_a=\sqrt a=0.1, so θa≈0.1\theta_a\approx0.1 and π/(4θa)≈7.8\pi/(4\theta_a)\approx7.8: 77 rounds give sin⁡2(15θa)≈0.995\sin^2(15\theta_a)\approx0.995. Classical repetition needs about 100100 tries for comparable success: 1/a1/\sqrt a versus 1/a1/a.

Question 4

Grover's algorithm on SAT with n=100n=100 variables and a single satisfying assignment needs about how many oracle calls?

  1. About 1002100^2
  2. About 250≈10152^{50}\approx10^{15}
  3. About 21002^{100}
  4. About 100100
Show the answer

B. About 250≈10152^{50}\approx10^{15}

The search space has N=2100N=2^{100} assignments, so π4N≈0.8×250≈1015\frac{\pi}{4}\sqrt N\approx0.8\times2^{50}\approx10^{15}. A quadratic improvement on brute force, but still exponential in nn.

Question 5

Which statement about one Grover iteration on nn qubits is correct?

  1. It uses one query and O(n)O(n) further gates, and the diffusion does not depend on which item is marked
  2. The diffusion must be redesigned for every marked item
  3. It needs about 2n2^n gates, because it acts on all 2n2^n amplitudes
  4. It needs no query: the diffusion alone finds the marked item
Show the answer

A. It uses one query and O(n)O(n) further gates, and the diffusion does not depend on which item is marked

D=H⊗n(2∣0n⟩ ⁣⟨0n∣−I)H⊗nD=H^{\otimes n}(2\dyad{0^n}-\id)H^{\otimes n} uses 2n2n Hadamards, 2n2n XX gates and one Cn−1ZC^{n-1}Z (O(n)O(n) gates with ancillas). Only the oracle knows the marked item.

Go deeper

Further reading

  • L. K. Grover, "A fast quantum mechanical algorithm for database search", Proc. 28th ACM STOC, 212–219 (1996).
  • M. Boyer, G. Brassard, P. Høyer & A. Tapp, "Tight bounds on quantum searching", Fortschritte der Physik 46, 493–505 (1998).
  • G. Brassard, P. Høyer, M. Mosca & A. Tapp, "Quantum amplitude amplification and estimation", Contemporary Mathematics 305, 53–74 (2002); arXiv:quant-ph/0005055.
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, ch. 6 (Cambridge, 10th anniv. ed., 2010).