Originally published on malcolmlow.net
Grover's algorithm is a quantum search procedure that locates a marked item in an unsorted list of N items in O(√N) oracle queries — a quadratic speedup over any classical approach. For N = 8 (3 qubits), this means roughly ⌊π/4 × √8⌋ = 2 optimal iterations before the probability of measuring the target state peaks.
This walkthrough tracks the exact amplitude of every basis state through each gate operation for the 3-qubit case, with target state |101⟩. All arithmetic is shown so each step can be verified by hand.
Structure of each iteration (Grover operator G):
Oracle Uf — Phase-flips the target state: |x⟩ → −|x⟩ if f(x) = 1, otherwise |x⟩ → |x⟩
Diffusion operator D = H⊗n(2|0⟩⟨0| − I)H⊗n — Reflects all amplitudes about their mean, amplifying the marked state at the expense of the others
Key insight: The oracle introduces destructive interference at the target, which the diffusion operator converts into constructive interference by inverting amplitudes about their mean. Each iteration rotates the state vector by angle 2θ closer to the target, where sin(θ) = 1/√N.
Phase 0: Initialization
Apply H⊗3 to |000⟩ to create a uniform superposition over all 8 basis states:
|ψinit⟩ = (1/√8)[ |000⟩ + |001⟩ + |010⟩ + |011⟩
+ |100⟩ + |101⟩ + |110⟩ + |111⟩ ]
Every state has amplitude +1/√8 ≈ 0.3535 and probability 12.5%.
Hadamard Reference (Standard Signs)
Element (i, j) has sign (−1)^popcount(i AND j). This table is used in every Hadamard step below — each row shows how an input basis state distributes into all 8 output states.
|000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
─────────────────────────────────────────────────
H|000⟩ → + + + + + + + +
H|001⟩ → + − + − + − + −
H|010⟩ → + + − − + + − −
H|011⟩ → + − − + + − − +
H|100⟩ → + + + + − − − −
H|101⟩ → + − + − − + − +
H|110⟩ → + + − − − − + +
H|111⟩ → + − − + − + + −
Round 1: Oracle → Diffusion
Step 3 — Oracle Uf
The oracle recognises |101⟩ as the marked state and flips its amplitude from +1/√8 to −1/√8. All other amplitudes remain unchanged. The superposition is preserved — no measurement is made.
Step 4.1 — First H (mapping to Hadamard basis)
Each input state contributes ±1/8 to each output column via the sign table. The oracle-marked |101⟩ row is fully sign-inverted.
|000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
──────────────────────────────────────────────────────────
+H|000⟩ (+1/√8) +1/8 +1/8 +1/8 +1/8 +1/8 +1/8 +1/8 +1/8
+H|001⟩ (+1/√8) +1/8 -1/8 +1/8 -1/8 +1/8 -1/8 +1/8 -1/8
+H|010⟩ (+1/√8) +1/8 +1/8 -1/8 -1/8 +1/8 +1/8 -1/8 -1/8
+H|011⟩ (+1/√8) +1/8 -1/8 -1/8 +1/8 +1/8 -1/8 -1/8 +1/8
+H|100⟩ (+1/√8) +1/8 +1/8 +1/8 +1/8 -1/8 -1/8 -1/8 -1/8
-H|101⟩ (-1/√8) -1/8 +1/8 -1/8 +1/8 +1/8 -1/8 +1/8 -1/8 ← oracle row
+H|110⟩ (+1/√8) +1/8 +1/8 -1/8 -1/8 -1/8 -1/8 +1/8 +1/8
+H|111⟩ (+1/√8) +1/8 -1/8 -1/8 +1/8 -1/8 +1/8 +1/8 -1/8
───────────────────────────────────────────────────────────────────
Net 4.1 +6/8 +2/8 -2/8 +2/8 +2/8 -2/8 +2/8 -2/8
Step 4.2 — Phase Flip (2|0⟩⟨0|−I)
Keep |000⟩ unchanged, negate all other states. This is the heart of inversion-about-the-mean.
|000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Post-Z: +6/8 -2/8 +2/8 -2/8 -2/8 +2/8 -2/8 +2/8
Step 4.3 — Second H (back to computational basis)
|000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Net R1 (exact): +4/8√8 +4/8√8 +4/8√8 +4/8√8 +4/8√8 +20/8√8 +4/8√8 +4/8√8
Net R1 (decimal): 0.177 0.177 0.177 0.177 0.177 0.884 0.177 0.177
After Round 1, |101⟩ has been amplified from 0.354 to 0.884.
Round 2: Oracle → Diffusion
Step 5 — Oracle Uf
The oracle flips |101⟩ from +20/8√8 to −20/8√8. The 7 non-target states remain at +4/8√8. This large asymmetry drives even stronger constructive interference in the diffusion step.
Step 6.1 — First H
|000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
──────────────────────────────────────────────────────────────────
+H|000⟩ (+4/8√8) +4/64 +4/64 +4/64 +4/64 +4/64 +4/64 +4/64 +4/64
+H|001⟩ (+4/8√8) +4/64 -4/64 +4/64 -4/64 +4/64 -4/64 +4/64 -4/64
+H|010⟩ (+4/8√8) +4/64 +4/64 -4/64 -4/64 +4/64 +4/64 -4/64 -4/64
+H|011⟩ (+4/8√8) +4/64 -4/64 -4/64 +4/64 +4/64 -4/64 -4/64 +4/64
+H|100⟩ (+4/8√8) +4/64 +4/64 +4/64 +4/64 -4/64 -4/64 -4/64 -4/64
-H|101⟩ (-20/8√8) -20/64 +20/64 -20/64 +20/64 +20/64 -20/64 +20/64 -20/64 ← oracle row
+H|110⟩ (+4/8√8) +4/64 +4/64 -4/64 -4/64 -4/64 -4/64 +4/64 +4/64
+H|111⟩ (+4/8√8) +4/64 -4/64 -4/64 +4/64 -4/64 +4/64 +4/64 -4/64
──────────────────────────────────────────────────────────────────────────────
Net 6.1 +8/64 +24/64 -24/64 +24/64 +24/64 -24/64 +24/64 -24/64
Step 6.2 — Phase Flip
|000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Post-Z: +8/64 -24/64 +24/64 -24/64 -24/64 +24/64 -24/64 +24/64
Step 6.3 — Second H
|000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Net R2 (exact): -16/64√8 -16/64√8 -16/64√8 -16/64√8 -16/64√8 +176/64√8 -16/64√8 -16/64√8
Net R2 (decimal): -0.088 -0.088 -0.088 -0.088 -0.088 +0.972 -0.088 -0.088
Success Probability after Round 2: P(|101⟩) = |0.972|² ≈ 94.5%
Round 2 is the optimal stopping point for 3-qubit Grover search — ⌊π/4 × √8⌋ = 2 iterations.
Round 3: The Overcooking Effect
Step 7 — Oracle Uf
With P(|101⟩) at 94.5%, one more iteration is one too many. The oracle flips |101⟩ from +176/64√8 to −176/64√8. The state vector has been rotated 2θ past its peak — a third diffusion step pushes it further away from the target, not closer.
Steps 8.1–8.3 — Diffusion
|000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Net R3 (exact): -448/512√8 (×7 non-target states) +832/512√8 (target)
Net R3 (decimal): -0.309 -0.309 -0.309 -0.309 -0.309 +0.575 -0.309 -0.309
P(|101⟩) = |0.575|² ≈ 33.0%
Summary: Amplitude Evolution Across Rounds
Round Target |101⟩ Non-target states P(|101⟩)
──────────────────────────────────────────────────────
Init +0.354 +0.354 12.5%
R1 +0.884 +0.177 78.1%
R2 +0.972 -0.088 94.5% ← optimal stop
R3 +0.575 -0.309 33.0% ← overcooked
The state vector has rotated past the optimal angle. P(|101⟩) drops from 94.5% to 33.0% — a significant fall, but |101⟩ still has more than double the probability of any other state. The algorithm has not lost the answer; it has merely overshot the maximum.
Importantly, the target amplitude is still positive (+0.575) — the vector has not crossed zero, it has simply overshot past the maximum. The result comes directly from the Born rule: P(|101⟩) = |amplitude|² = |+0.575|² ≈ 0.330.
Quantum Series 2026 · Built with Qiskit 1.x