Reconstructing Grover's Algorithm

Deriving quantum search from first principles — why amplitude amplification works, and why √N is the natural stopping point.

Problem

We are given oracle access to a function $f : \{0,1\}^n \to \{0,1\}$ which marks exactly one item: $f(w) = 1$ for a single unknown $w$ , and $f(x) = 0$ otherwise. Classically, finding $w$ requires $\Theta(N)$ queries where $N = 2^n$ . How fast can a quantum computer find $w$ ?

Initial Observations

A quantum state can hold all $N$ candidates in superposition — but measuring the uniform superposition only finds $w$ with probability $1/N$ .
The oracle can flip the phase of the marked item: $O|x\rangle = (-1)^{f(x)}|x\rangle$ .
A phase is invisible to measurement. We need some way to convert phase information into amplitude information.
Repeating something that "nudges" amplitude toward $w$ might compound.

IdeaPhase flip + inversion about the meanAC

Key Question

What unitary operation converts a phase difference into an amplitude difference?

Write It Out

Start with the uniform superposition $|s\rangle = \frac{1}{\sqrt{N}}\sum_x |x\rangle$ . After the oracle, the state is the same except the amplitude on $|w\rangle$ is negative. The mean amplitude is now slightly below $\frac{1}{\sqrt{N}}$ . If we reflect every amplitude about the mean, the negative amplitude on $|w\rangle$ lands far above the mean — roughly $\frac{3}{\sqrt{N}}$ — while every other amplitude shrinks slightly.

The reflection about the mean is the operator

D = 2|s\rangle\langle s| - I

and one Grover iteration is $G = D \cdot O$ .

Lemma.

The state always remains in the 2-dimensional plane spanned by $|w\rangle$ and $|s\rangle$ , and each Grover iteration is a rotation in that plane by angle $2\theta$ , where $\sin\theta = \frac{1}{\sqrt{N}}$ .

Proof.

Both reflections — the oracle (a reflection about the hyperplane orthogonal to $|w\rangle$ ) and $D$ (a reflection about $|s\rangle$ ) — preserve the plane $\mathrm{span}\{|w\rangle, |s\rangle\}$ . The composition of two reflections is a rotation by twice the angle between the reflection axes, which is $2\theta$ .

∎

Corollary.

After $k$ iterations the state makes angle $(2k+1)\theta$ with the axis orthogonal to $|w\rangle$ . Choosing $k \approx \frac{\pi}{4}\sqrt{N}$ brings the state within angle $\theta$ of $|w\rangle$ , so measurement finds $w$ with probability $1 - O(1/N)$ .

Lesson

Grover's algorithm is not "trying everything in parallel" — it is a slow rotation from $|s\rangle$ toward $|w\rangle$ , driven by two reflections. The $\sqrt{N}$ arises because each iteration rotates by a fixed angle $\approx 2/\sqrt{N}$ . Over-rotating past $|w\rangle$ decreases the success probability — running the loop longer makes the answer worse.

Implementation

from qiskit import QuantumCircuit
from qiskit.circuit.library import GroverOperator, MCMTGate, ZGate
import math
 
n = 5                       # qubits; N = 32
marked = "10110"            # the unknown w (for the demo oracle)
 
oracle = QuantumCircuit(n)
for i, bit in enumerate(reversed(marked)):
    if bit == "0":
        oracle.x(i)
oracle.append(MCMTGate(ZGate(), n - 1, 1), range(n))
for i, bit in enumerate(reversed(marked)):
    if bit == "0":
        oracle.x(i)
 
grover_op = GroverOperator(oracle)
 
qc = QuantumCircuit(n)
qc.h(range(n))                                   # |s>
iterations = math.floor(math.pi / 4 * math.sqrt(2**n))
for _ in range(iterations):
    qc.compose(grover_op, inplace=True)          # G = D * O
qc.measure_all()

Review

The reconstruction hinged on three moves: (1) realizing a phase flip alone is useless without a second operation, (2) asking what reflection geometry does to a single outlier amplitude, and (3) recognizing two reflections compose into a rotation — at which point the $\frac{\pi}{4}\sqrt{N}$ stopping rule stops being magic and becomes trigonometry.