Lesson 21: Grover's Algorithm: Oracle and Diffusion Operator¶
21.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- State the unstructured search problem and the classical query bound.
- Construct the Grover oracle \(O_f\) and describe its action geometrically.
- Derive the diffusion operator \(D = 2|\psi\rangle\langle\psi| - I\) and prove it performs inversion about the mean.
- Trace the amplitudes through one and two Grover iterations by hand.
- Build the full Grover circuit for a small \(n\).
21.2 The Problem¶
Unstructured search. Given an oracle for \(f:\{0,1\}^n\to\{0,1\}\) with \(f(w) = 1\) for exactly one "marked" item \(w\) and \(f(x)=0\) otherwise, find \(w\).
Equivalently: search an unsorted database of \(N = 2^n\) items for the one satisfying a predicate. No structure, no sorting, no index — the only access is to query the predicate.
Classical. Every query eliminates one candidate. Worst case \(N\) queries; average \(N/2\); randomised expected \(\approx N/2\). Lower bound \(\Omega(N)\).
Quantum (Grover, 1996).
Applications. Any brute-force search: cryptographic key search, SAT/constraint satisfaction, graph colouring, collision finding, minimum finding, and as a subroutine inside larger algorithms (amplitude amplification).
21.3 Setup¶
Uniform superposition.
Every amplitude is \(\frac{1}{\sqrt N}\), so \(\Pr[w] = \frac1N\) — measuring now is just random guessing. Grover's algorithm grows the amplitude of \(|w\rangle\) at the expense of the others.
Two useful vectors. Split the space into "the marked item" and "everything else":
These are orthonormal, and
Everything happens in this 2-dimensional plane — a fact exploited fully in L22.
21.4 The Two Operators¶
The oracle (phase inversion)¶
As an operator,
Check: \(O_f|w\rangle = |w\rangle - 2|w\rangle = -|w\rangle\) ✓; \(O_f|x\rangle = |x\rangle\) for \(x\perp w\) ✓.
Implementation. Build the Boolean circuit for \(f\) with a \(|-\rangle\) ancilla and use phase kick-back (L11). For \(w\) given explicitly: apply \(X\) gates to flip the 0-bits of \(w\) to 1, apply a multi-controlled \(Z\), then undo the \(X\) gates.
Geometrically: \(O_f\) is a reflection about \(|w^\perp\rangle\) — it flips the \(|w\rangle\) component and leaves the orthogonal complement alone.
Note: the oracle alone changes no probability, since \(|-1|^2 = 1\). It marks; it does not amplify. Amplification is the diffusion operator's job.
The diffusion operator (inversion about the mean)¶
Circuit form. Since \(|\psi\rangle = H^{\otimes n}|0\rangle\):
The inner operator \(2|0\rangle\langle0| - I\) flips the sign of every basis state except \(|0\cdots0\rangle\); up to a global \(-1\) it is a multi-controlled \(Z\) conjugated by \(X\) gates.
Implementation:
D = H^n -- X^n -- [multi-controlled Z on all n qubits] -- X^n -- H^n
Unitarity check. \(D^\dagger = D\) (both terms Hermitian) and
using \(\langle\psi|\psi\rangle=1\). So \(D\) is Hermitian, unitary and self-inverse — a reflection.
Why D is "inversion about the mean"¶
Let the state be \(|\phi\rangle = \sum_x \alpha_x|x\rangle\) and let
be the mean amplitude. Then
so
Each amplitude is reflected about the mean. An amplitude below the mean by \(\delta\) ends up above it by \(\delta\), and vice versa.
This is precisely why Grover works. The oracle makes \(\alpha_w\) negative, which pulls the mean slightly down but leaves it positive. Reflecting \(\alpha_w\) (a negative number) about a positive mean sends it to a large positive value, while the unmarked amplitudes, already near the mean, barely move — they shrink slightly to conserve the norm.
21.5 The Grover Iteration¶
Full algorithm.
1. Prepare |0>^n
2. Apply H^n -> uniform superposition
3. Repeat k = floor(pi/4 * sqrt(N)) times:
apply O_f (mark: flip sign of |w>)
apply D (amplify: invert about the mean)
4. Measure -> w with high probability
Circuit.
|0> --[H]--+-------------+--+-------------+-- ... --[M]--
|0> --[H]--| Oracle |--| Diffusion |-- ...
|0> --[H]--| O_f |--| D |-- ...
+-------------+ +-------------+
\_______________________________/
repeat k times
Critical warning. More iterations are not better. The amplitude oscillates sinusoidally, and running past the optimum makes the success probability decrease. This "over-rotation" is analysed in L22.
21.6 Solved Problems¶
Problem 1 — Amplitude table for N = 4, one iteration¶
Let \(n=2\), \(N=4\), marked item \(w = |10\rangle\). Compute the amplitudes after one Grover iteration.
Solution.
Initial state. All amplitudes \(\frac{1}{\sqrt4} = 0.5\):
Step 1 — oracle. Flip the sign of \(\alpha_{10}\):
Step 2 — diffusion. Mean:
Apply \(\alpha \mapsto 2\bar\alpha - \alpha = 0.5 - \alpha\):
| \(x\) | before | \(0.5 - \alpha\) | after |
|---|---|---|---|
| 00 | \(0.5\) | \(0.5-0.5\) | \(0\) |
| 01 | \(0.5\) | \(0.5-0.5\) | \(0\) |
| 10 | \(-0.5\) | \(0.5+0.5\) | \(\mathbf{1}\) |
| 11 | \(0.5\) | \(0.5-0.5\) | \(0\) |
One iteration finds the answer with certainty for \(N = 4\).
Why exactly? The optimal count is \(\frac{\pi}{4}\sqrt4 = \frac{\pi}{2} \approx 1.57\), and the exact requirement (L22) is \(\theta = \arcsin(1/2) = 30°\) with \((2k+1)\theta = 90°\), giving \(k = 1\) exactly. \(N=4\) is the unique case where Grover is exact.
Classical comparison: 2.5 queries on average, 4 in the worst case. Quantum: 1.
Problem 2 — Two iterations for N = 8¶
\(n=3\), \(N=8\), \(w = |101\rangle\). Compute amplitudes after one and two iterations.
Solution.
Initial: all \(\alpha = \frac{1}{\sqrt8} = 0.35355\).
Iteration 1.
Oracle: \(\alpha_w = -0.35355\); others \(+0.35355\).
Mean: \(\bar\alpha = \frac{7(0.35355) - 0.35355}{8} = \frac{6\times0.35355}{8} = 0.26517\).
Diffusion: \(\alpha\mapsto 2(0.26517) - \alpha = 0.53033 - \alpha\).
Check normalisation: \(0.88388^2 + 7(0.17678)^2 = 0.78125 + 0.21875 = 1\) ✓.
Iteration 2.
Oracle: \(\alpha_w = -0.88388\); others \(0.17678\).
Mean: \(\bar\alpha = \frac{-0.88388 + 7(0.17678)}{8} = \frac{-0.88388+1.23744}{8} = \frac{0.35355}{8} = 0.04419\).
Diffusion: \(\alpha\mapsto 0.08839 - \alpha\).
Check: \(0.97227^2 + 7(0.08839)^2 = 0.94531 + 0.05469 = 1\) ✓.
Optimal count: \(\lfloor\frac{\pi}{4}\sqrt8\rfloor = \lfloor 2.22\rfloor = 2\) ✓ — two iterations is right, and 94.5 % is the achievable maximum for \(N=8\).
Compare classical: 4 queries on average.
Problem 3 — Over-rotation: what happens with too many iterations¶
Continue Problem 2 to a third and fourth iteration.
Solution.
Iteration 3. Start from \(\alpha_w = 0.97227\), others \(-0.08839\).
Oracle: \(\alpha_w = -0.97227\).
Mean: \(\bar\alpha = \frac{-0.97227 + 7(-0.08839)}{8} = \frac{-0.97227 - 0.61872}{8} = \frac{-1.59099}{8} = -0.19887\).
Diffusion: \(\alpha\mapsto -0.39775 - \alpha\).
The success probability has fallen from 94.5 % to 33 %.
Iteration 4 (continuing the same computation) drops it further, to about 1.2 % — below the \(\frac18 = 12.5\%\) of the initial state.
Summary table for \(N=8\):
| Iterations \(k\) | \(\Pr[w]\) |
|---|---|
| 0 | 12.5 % |
| 1 | 78.1 % |
| 2 | 94.5 % |
| 3 | 33.0 % |
| 4 | 1.2 % |
| 5 | 54.8 % |
The probability oscillates with period \(\approx \pi/\theta\). This is the single most important practical caution about Grover: you must know \(N\) and the number of solutions in advance to stop at the right moment. When the number of solutions is unknown, use quantum counting (QPE applied to \(G\)) or the exponential-search trick of Boyer–Brassard–Høyer–Tapp.
Problem 4 — Building the oracle circuit¶
Construct the oracle circuit marking \(w = |1011\rangle\) on 4 qubits.
Solution.
The building block is the multi-controlled \(Z\) (\(C^3Z\)), which flips the sign of \(|1111\rangle\) only. We need the sign flipped on \(|1011\rangle\) instead.
Trick: conjugate by \(X\) gates on the positions where \(w\) has a 0.
Here \(w = 1011\), so position 2 (second from the left) is 0.
q0 : ------------*-----------
q1 : --[X]-------*----[X]----
q2 : ------------*-----------
q3 : -----------[Z]----------
where the *–[Z] structure is the multi-controlled \(Z\) with \(q_0,q_1,q_2\) as controls.
Verification. Input \(|1011\rangle\): after the \(X\) on \(q_1\) it becomes \(|1111\rangle\); \(C^3Z\) gives \(-|1111\rangle\); the second \(X\) returns \(-|1011\rangle\) ✓.
Input \(|1111\rangle\): after \(X\) on \(q_1\) it is \(|1011\rangle\); \(C^3Z\) does nothing (control \(q_1 = 0\)); the second \(X\) gives \(|1111\rangle\) ✓ — unmarked, as required.
Cost. A \(C^{n-1}Z\) decomposes into \(O(n)\) Toffoli gates using \(n-2\) ancillas, or \(O(n^2)\) elementary gates with no ancillas. For \(n=4\): 2 Toffolis + 1 \(CZ\) with one ancilla.
The honest caveat. Building the oracle here requires knowing \(w\) — circular for a demonstration. In real applications \(f\) is a predicate you can evaluate but whose satisfying assignment you do not know: a SAT formula, a hash-preimage test, a chess-position evaluator.
Problem 5 — Multiple marked items¶
Suppose \(M\) items are marked out of \(N\). Recompute the diffusion step for \(N=16\), \(M=4\) after one iteration, and state how the optimal iteration count changes.
Solution.
Initial: all \(\alpha = \frac{1}{4} = 0.25\).
Oracle: the 4 marked amplitudes become \(-0.25\); the 12 unmarked stay \(+0.25\).
Mean:
Diffusion: \(\alpha\mapsto 0.25 - \alpha\).
Check: \(4(0.5)^2 + 12(0)^2 = 1\) ✓.
One iteration gives certainty! Because \(\frac{M}{N} = \frac{4}{16} = \frac14\), i.e. \(\sin\theta = \frac12\), \(\theta = 30°\), and one iteration rotates by \(2\theta = 60°\), reaching \(3\theta = 90°\) — exactly the target axis (L22).
General optimal count.
Check: \(\frac{\pi}{4}\sqrt{16/4} = \frac{\pi}{4}\times2 = 1.57 \Rightarrow k = 1\) ✓.
More solutions ⟹ fewer iterations, as expected. But note the trap: if \(M\) is unknown you cannot compute \(k_{\text{opt}}\), and choosing wrongly can be worse than not running the algorithm. Quantum counting (QPE on \(G\), whose eigenphases encode \(\theta\)) estimates \(M\) in \(O(\sqrt N)\) queries and resolves this.
21.7 Practice Problems¶
- For \(N=4\), \(w=|00\rangle\): verify one iteration gives \(\Pr[w]=1\).
- For \(N=16\), \(M=1\): compute \(\Pr[w]\) after 1, 2 and 3 iterations. [Ans: ≈47.3 %, 90.8 %, 96.1 %]
- Compute \(k_{\text{opt}}\) for \(N=1024\), \(M=1\) and for \(M=16\). [Ans: 25 and 6]
- Show that \(D = H^{\otimes n}(2|0\rangle\langle0| - I)H^{\otimes n}\).
- Prove \(O_f^2 = I\) and \(D^2 = I\).
- Draw the oracle circuit for \(w = |0110\rangle\).
- Explain in one sentence why the oracle alone changes no measurement probability.
21.8 Summary¶
- Unstructured search: classical \(\Theta(N)\), quantum \(\Theta(\sqrt N)\) — a quadratic speed-up.
- Oracle \(O_f = I - 2|w\rangle\langle w|\) flips the sign of the marked amplitude — it marks but does not amplify.
- Diffusion \(D = 2|\psi\rangle\langle\psi| - I\) maps \(\alpha_x \mapsto 2\bar\alpha - \alpha_x\): inversion about the mean. Circuit: \(H^{\otimes n}\), \(X^{\otimes n}\), \(C^{n-1}Z\), \(X^{\otimes n}\), \(H^{\otimes n}\).
- One Grover iteration is \(G = D\,O_f\); repeat \(k_{\text{opt}} = \lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor\) times.
- The success probability oscillates — too many iterations makes things worse. Know \(M\), or use quantum counting.
- Special exact cases: \(N=4\) with \(M=1\), and \(N/M = 4\) generally, reach 100 % in one iteration.
Next lesson: L22 — Grover's algorithm: geometric analysis, optimal iteration count and the matching lower bound.
Practise now: unit2-algorithms-lab.html → Grover tab: choose \(N\) and the marked items, then
step through iterations watching the amplitude bars and the mean line move.