Grover’s Algorithm: Exact Mathematical Evolution
Full 3-Qubit Matrix Interference Walkthrough
What is Grover’s Algorithm? 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 then converts into constructive interference by inverting amplitudes about their mean. Each iteration rotates the state vector by an angle 2θ closer to the target, where sin(θ) = 1/√N.
| Init | Diffusion 1 | Diffusion 2 | ||||||||||||||||||
| |0⟩ | H | Uf | H | Z0 | H | Uf | H | Z0 | H | M | ||||||||||
| |0⟩ | H | H | H | H | H | M | ||||||||||||||
| |0⟩ | H | H | H | H | H | M | ||||||||||||||
| Iteration 1 | Iteration 2 · optimal | |||||||||||||||||||
Phase 0: Initialization
Steps 1 & 2: Apply H⊗3 to |000> to create a uniform superposition over all 8 basis states. Because each single-qubit Hadamard maps |0> to (|0>+|1>)/√2, applying all three simultaneously yields equal amplitude 1/√8 ≈ 0.3535 for every state. This is the starting point — every state is equally likely, and the algorithm has no preference yet.
Hadamard Reference (Standard Signs)
The 8×8 Walsh-Hadamard matrix defines the sign pattern when H⊗3 is applied to any basis state. Element (i, j) has sign (−1)popcount(i AND j) — i.e., the number of bit positions where both row state and column state have a 1. The actual amplitude contribution is this sign divided by √8. This table is used in every Hadamard step below: each row corresponds to one input basis state, and its sign pattern determines how it distributes into all 8 output states.
| Basis State | 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 applies a phase kickback, flipping its amplitude from +1/√8 to −1/√8. All other amplitudes remain unchanged. Physically, this encodes “this is the target” purely in phase — no measurement is made, so the superposition is preserved.
Step 4.1: Round 1 First Hadamard (H)
The diffusion operator begins by mapping from the computational basis back into the Hadamard basis. Each input state |x> with amplitude ax contributes ax/√8 to every output column, with sign given by the reference table. For all non-target states ax = +1/√8, so each cell = (+1/√8)×(Sign/√8) = Sign/8. For the oracle-marked |101>, the amplitude is −1/√8, so the entire row is sign-inverted (highlighted in red). The Net Result row is the vertical sum of all 8 rows for each column.
| Source (Post-Oracle) | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| +H|000> (1/√8) | +18 | +18 | +18 | +18 | +18 | +18 | +18 | +18 |
| +H|001> (1/√8) | +18 | -18 | +18 | -18 | +18 | -18 | +18 | -18 |
| +H|010> (1/√8) | +18 | +18 | -18 | -18 | +18 | +18 | -18 | -18 |
| +H|011> (1/√8) | +18 | -18 | -18 | +18 | +18 | -18 | -18 | +18 |
| +H|100> (1/√8) | +18 | +18 | +18 | +18 | -18 | -18 | -18 | -18 |
| -H|101> (-1/√8) | -18 | +18 | -18 | +18 | +18 | -18 | +18 | -18 |
| +H|110> (1/√8) | +18 | +18 | -18 | -18 | -18 | -18 | +18 | +18 |
| +H|111> (1/√8) | +18 | -18 | -18 | +18 | -18 | +18 | +18 | -18 |
| Net Result 4.1 | +68 | +28 | -28 | +28 | +28 | -28 | +28 | -28 |
Step 4.2: Round 1 Phase Flip (Z on non-|000>)
This step implements the 2|0><0|−I operator in the computational basis. In practice it means: keep |000>’s amplitude unchanged, and negate every other state. This is the heart of inversion-about-the-mean: because the |000> column accumulated the largest positive amplitude in Step 4.1 (reflecting the mean of all amplitudes before the first H), flipping everything else relative to it creates the inversion effect that will boost the target in the next step.
| State | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| Amp (Post-Z) | +68 | -28 | +28 | -28 | -28 | +28 | -28 | +28 |
Step 4.3: Round 1 Second Hadamard (H)
The second H maps the Hadamard-basis amplitudes from Step 4.2 back to the computational basis, completing the diffusion operator. Each post-Z amplitude contributes to every output column via the reference sign table, multiplied by 1/√8, giving denominators of 8√8. Summing column |101> yields +208√8 ≈ 0.884 — a dramatic amplification from the initial 0.354 — while all other states settle to +48√8 ≈ 0.177. One iteration is complete.
| Source (Post-Z) | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| +H|000> (68) | +68√8 | +68√8 | +68√8 | +68√8 | +68√8 | +68√8 | +68√8 | +68√8 |
| -H|001> (-28) | -28√8 | +28√8 | -28√8 | +28√8 | -28√8 | +28√8 | -28√8 | +28√8 |
| +H|010> (28) | +28√8 | +28√8 | -28√8 | -28√8 | +28√8 | +28√8 | -28√8 | -28√8 |
| -H|011> (-28) | -28√8 | +28√8 | +28√8 | -28√8 | -28√8 | +28√8 | +28√8 | -28√8 |
| -H|100> (-28) | -28√8 | -28√8 | -28√8 | -28√8 | +28√8 | +28√8 | +28√8 | +28√8 |
| +H|101> (28) | +28√8 | -28√8 | +28√8 | -28√8 | -28√8 | +28√8 | -28√8 | +28√8 |
| -H|110> (-28) | -28√8 | -28√8 | +28√8 | +28√8 | +28√8 | +28√8 | -28√8 | -28√8 |
| +H|111> (28) | +28√8 | -28√8 | -28√8 | +28√8 | -28√8 | +28√8 | +28√8 | -28√8 |
| Net Result (R1) | +48√8 | +48√8 | +48√8 | +48√8 | +48√8 | +208√8 | +48√8 | +48√8 |
| Decimal (R1) | 0.177 | 0.177 | 0.177 | 0.177 | 0.177 | 0.884 | 0.177 | 0.177 |
Round 2: [Oracle → Diffusion]
Step 5: Oracle Uf — The oracle is applied again to the post-R1 state. |101> now carries a much larger amplitude (+208√8), so the phase flip to −208√8 creates a far more pronounced imbalance. The 7 non-target states each carry only +48√8. This large asymmetry is what will drive even stronger constructive interference in the diffusion step.
Step 6.1: Round 2 First Hadamard (H)
Each amplitude is multiplied by 1/√8 as it spreads across the 8 columns via the reference sign table. The denominator becomes 8√8 × √8 = 64. The 7 uniform states (+48√8) form balanced Walsh-Hadamard rows that cancel perfectly for all non-|000> columns — only the oracle-perturbed |101> row breaks the symmetry, contributing an extra −24 or +24 to each non-zero column (depending on the H sign for that bit pattern). Column |000> is special: all 8 rows contribute positively, giving +864.
| Source (Post-Oracle) | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| +H|000> (48√8) | +464 | +464 | +464 | +464 | +464 | +464 | +464 | +464 |
| +H|001> (48√8) | +464 | -464 | +464 | -464 | +464 | -464 | +464 | -464 |
| +H|010> (48√8) | +464 | +464 | -464 | -464 | +464 | +464 | -464 | -464 |
| +H|011> (48√8) | +464 | -464 | -464 | +464 | +464 | -464 | -464 | +464 |
| +H|100> (48√8) | +464 | +464 | +464 | +464 | -464 | -464 | -464 | -464 |
| -H|101> (-208√8) | -2064 | +2064 | -2064 | +2064 | +2064 | -2064 | +2064 | -2064 |
| +H|110> (48√8) | +464 | +464 | -464 | -464 | -464 | -464 | +464 | +464 |
| +H|111> (48√8) | +464 | -464 | -464 | +464 | -464 | +464 | +464 | -464 |
| Net Result 6.1 | +864 | +2464 | -2464 | +2464 | +2464 | -2464 | +2464 | -2464 |
Step 6.2: Phase Flip (Z on non-|000>)
Same operation as Step 4.2: negate every amplitude except |000>. The |000> column retains its +864 value. All other states flip sign, converting e.g. +2464 → −2464. This primes the second Hadamard to route amplitude toward the target state.
| State | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| Amp (Post-Z) | +864 | -2464 | +2464 | -2464 | -2464 | +2464 | -2464 | +2464 |
Step 6.3: Round 2 Second Hadamard (H)
The final H of the diffusion operator maps the post-Z amplitudes back to the computational basis. Each amplitude propagates through the Hadamard sign table with denominator 64√8. Column |101> receives a constructive sum of +17664√8 ≈ 0.972 — near-certain success. The non-target states all land at −1664√8 ≈ −0.088, where the negative sign carries no measurement consequence. This is the optimal stopping point for 3-qubit Grover search: stopping here gives the highest possible P(|101>).
| Source (Post-Z) | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| +H|000> (864) | +864√8 | +864√8 | +864√8 | +864√8 | +864√8 | +864√8 | +864√8 | +864√8 |
| -H|001> (-2464) | -2464√8 | +2464√8 | -2464√8 | +2464√8 | -2464√8 | +2464√8 | -2464√8 | +2464√8 |
| +H|010> (2464) | +2464√8 | +2464√8 | -2464√8 | -2464√8 | +2464√8 | +2464√8 | -2464√8 | -2464√8 |
| -H|011> (-2464) | -2464√8 | +2464√8 | +2464√8 | -2464√8 | -2464√8 | +2464√8 | +2464√8 | -2464√8 |
| -H|100> (-2464) | -2464√8 | -2464√8 | -2464√8 | -2464√8 | +2464√8 | +2464√8 | +2464√8 | +2464√8 |
| +H|101> (2464) | +2464√8 | -2464√8 | +2464√8 | -2464√8 | -2464√8 | +2464√8 | -2464√8 | +2464√8 |
| -H|110> (-2464) | -2464√8 | -2464√8 | +2464√8 | +2464√8 | +2464√8 | +2464√8 | -2464√8 | -2464√8 |
| +H|111> (2464) | +2464√8 | -2464√8 | -2464√8 | +2464√8 | -2464√8 | +2464√8 | +2464√8 | -2464√8 |
| Net Result (R2) | -1664√8 | -1664√8 | -1664√8 | -1664√8 | -1664√8 | +17664√8 | -1664√8 | -1664√8 |
| Decimal (R2) | -0.088 | -0.088 | -0.088 | -0.088 | -0.088 | +0.972 | -0.088 | -0.088 |
Round 3: [Oracle → Diffusion] (The Overcooking Effect)
Step 7: Oracle Uf — With P(|101>) at 94.5%, one more iteration is one too many. The oracle again flips |101>’s amplitude: +17664√8 → −17664√8. The 7 non-target states each remain at −1664√8. The state vector has been rotated 2θ past its peak, and a third diffusion step will push it further away from the target, not closer.
Step 8.1: Round 3 First Hadamard (H)
The denominator grows to 512 (= 64√8 × √8). All 8 input amplitudes are now negative (after the oracle flip, |101> is −17664√8 and the rest are −1664√8), so the |000> column accumulates a strongly negative sum (−288512). The non-|000> columns are dominated by the large −|101> row contribution, which is sign-inverted from the reference table and therefore contributes ±176512. The net result is a lopsided distribution that the phase flip will convert into a push away from the target.
| Source (Post-Oracle) | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| -H|000> (-1664√8) | -16512 | -16512 | -16512 | -16512 | -16512 | -16512 | -16512 | -16512 |
| -H|001> (-1664√8) | -16512 | +16512 | -16512 | +16512 | -16512 | +16512 | -16512 | +16512 |
| -H|010> (-1664√8) | -16512 | -16512 | +16512 | +16512 | -16512 | -16512 | +16512 | +16512 |
| -H|011> (-1664√8) | -16512 | +16512 | +16512 | -16512 | -16512 | +16512 | +16512 | -16512 |
| -H|100> (-1664√8) | -16512 | -16512 | -16512 | -16512 | +16512 | +16512 | +16512 | +16512 |
| -H|101> (-17664√8) | -176512 | +176512 | -176512 | +176512 | +176512 | -176512 | +176512 | -176512 |
| -H|110> (-1664√8) | -16512 | -16512 | +16512 | +16512 | +16512 | +16512 | -16512 | -16512 |
| -H|111> (-1664√8) | -16512 | +16512 | +16512 | -16512 | +16512 | -16512 | -16512 | +16512 |
| Net Result 8.1 | -288512 | +160512 | -160512 | +160512 | +160512 | -160512 | +160512 | -160512 |
Step 8.2: Round 3 Phase Flip (Z on non-|000>)
The |000> amplitude (−288512) is preserved. All other amplitudes flip sign. Notice that after R2 the non-target states had small negative amplitudes; after the phase flip here they become positive (+160512), while the target column was −160512 and now becomes +160512 as well — the diffusion has lost its asymmetry and will no longer strongly favour |101>.
| State | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| Amp (Post-Z) | -288512 | -160512 | +160512 | -160512 | -160512 | +160512 | -160512 | +160512 |
Step 8.3: Round 3 Second Hadamard (H)
The second H maps amplitudes back to the computational basis with denominators of 512√8. The large negative |000> amplitude now spreads destructive interference broadly, while the relatively uniform positive amplitudes for the remaining states partially cancel in the |101> column. The result is +832512√8 = +138√8 ≈ +0.575 for |101> and −448512√8 = −78√8 ≈ −0.309 for all non-target states. P(|101>) has fallen to ~33%, demonstrating that iterating past the optimal count hurts. Importantly, |101> still leads every other state by 3×, so a single extra iteration only partially degrades the result — it has not catastrophically lost the solution.
| Source (Post-Z) | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| -H|000> (-288512) | -288512√8 | -288512√8 | -288512√8 | -288512√8 | -288512√8 | -288512√8 | -288512√8 | -288512√8 |
| -H|001> (-160512) | -160512√8 | +160512√8 | -160512√8 | +160512√8 | -160512√8 | +160512√8 | -160512√8 | +160512√8 |
| +H|010> (160512) | +160512√8 | +160512√8 | -160512√8 | -160512√8 | +160512√8 | +160512√8 | -160512√8 | -160512√8 |
| -H|011> (-160512) | -160512√8 | +160512√8 | +160512√8 | -160512√8 | -160512√8 | +160512√8 | +160512√8 | -160512√8 |
| -H|100> (-160512) | -160512√8 | -160512√8 | -160512√8 | -160512√8 | +160512√8 | +160512√8 | +160512√8 | +160512√8 |
| +H|101> (160512) | +160512√8 | -160512√8 | +160512√8 | -160512√8 | -160512√8 | +160512√8 | -160512√8 | +160512√8 |
| -H|110> (-160512) | -160512√8 | -160512√8 | +160512√8 | +160512√8 | +160512√8 | +160512√8 | -160512√8 | -160512√8 |
| +H|111> (160512) | +160512√8 | -160512√8 | -160512√8 | +160512√8 | -160512√8 | +160512√8 | +160512√8 | -160512√8 |
| Net Result (R3) | -448512√8 | -448512√8 | -448512√8 | -448512√8 | -448512√8 | +832512√8 | -448512√8 | -448512√8 |
| Simplified (R3) | -78√8 | -78√8 | -78√8 | -78√8 | -78√8 | +138√8 | -78√8 | -78√8 |
| Decimal (R3) | -0.309 | -0.309 | -0.309 | -0.309 | -0.309 | +0.575 | -0.309 | -0.309 |
⚠ Overcooking Confirmed — But Not Catastrophic
The state vector has rotated past the optimal angle. P(|101>) drops from 94.5% (R2) 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 de-amplified it. Note also that the target amplitude is still positive (+0.575) — the vector has not crossed zero, it has simply overshot past the maximum. The 33.0% comes directly from the Born rule: P(|101>) = |amplitude|² = |+0.575|² ≈ 0.330.
Techucation 