Quantum Computing: Grover's Algorithm — Inversion About t...

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

推荐订阅源

DEV Community