One Grover Iteration

A single Grover iteration is the atomic unit of Grover's search algorithm. It combines two operations you have already seen — the phase-kickback oracle and the diffuser — into one amplification step that rotates the state closer to the marked item.

The structure of one iteration

Starting from a uniform superposition $|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}$ over all $N = 2^n$ basis states, a single Grover iteration applies:

$G = D \cdot U_f$

where $U_f$ is the oracle (phase-flip on the marked state $|x^*\rangle$ ) and $D$ is the diffuser (reflection about the mean amplitude).

The oracle

The oracle marks the target by flipping its sign:

$U_f |x\rangle = \begin{cases} -|x\rangle & \text{if } x = x^* \\ |x\rangle & \text{otherwise} \end{cases}$

After $U_f$ , the marked amplitude has become negative while all others remain positive. The average amplitude drops slightly below its starting value of $1/\sqrt{N}$ .

The diffuser

The diffuser reflects every amplitude about their (new) mean:

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

Any amplitude above the mean grows; any amplitude below the mean grows even more (since the marked amplitude is now the most below-average item). After one full iteration:

The marked amplitude increases by approximately $2/\sqrt{N}$ .
All unmarked amplitudes decrease by approximately $2/(N\sqrt{N})$ .

Geometric picture

In the two-dimensional plane spanned by $|x^*\rangle$ and $|s_\perp\rangle$ (the uniform superposition over unmarked states), the oracle is a reflection across the horizontal axis and the diffuser is a reflection across $|s\rangle$ . Their composition is a rotation by angle $2\theta$ , where $\sin\theta = 1/\sqrt{N}$ . Starting at angle $\theta$ from the horizontal, each iteration adds $2\theta$ , so after $k$ iterations the angle is $(2k+1)\theta$ . The optimal number of iterations is $k^* \approx \tfrac{\pi}{4}\sqrt{N}$ , which puts the state closest to $|x^*\rangle$ .

Building one iteration in a circuit

For a two-qubit search space with the marked state $|11\rangle$ , the complete single iteration is:

Initialise with $H \otimes H$ to reach the uniform superposition.
Oracle — a $CZ$ gate phase-flips $|11\rangle$ .
Diffuser — the standard $n$ -qubit diffuser circuit: $H^{\otimes 2}\, X^{\otimes 2}\, CZ\, X^{\otimes 2}\, H^{\otimes 2}$

Written as a sequence of gates:

$|00\rangle \xrightarrow{H\otimes H} |s\rangle \xrightarrow{CZ} U_f|s\rangle \xrightarrow{D} G|s\rangle \approx |11\rangle$

After this single iteration the probability of measuring $|11\rangle$ is exactly $1$ .

Try it

Your task is to build one complete Grover iteration for a two-qubit system that marks $|10\rangle$ . The oracle that marks $|10\rangle$ phase-flips the state where qubit 0 is $|1\rangle$ and qubit 1 is $|0\rangle$ . Use an $X$ on qubit 1 to map $|10\rangle \to |11\rangle$ , apply $CZ$ , then undo the $X$ .

Run your code to see the quantum state.

After running your circuit, the distribution should place all probability on the bitstring 10. That is amplitude amplification at work: one well-chosen reflection pair is enough to find one item among four with certainty.