The Diffuser (Inversion About Mean)

Each Grover iteration has two steps: the oracle and the diffuser. While the oracle flips the phase of the marked item, the diffuser does the complementary job — it reflects all amplitudes about their mean, amplifying the marked amplitude and suppressing the rest.

Inversion about the mean

Suppose the current state has amplitudes $a_0, a_1, \dots, a_{N-1}$ and their average is $\mu = \frac{1}{N}\sum_{x} a_x$. The inversion-about-mean map sends each amplitude to

$a_x \;\longmapsto\; 2\mu - a_x.$

If the marked item has had its amplitude flipped negative by the oracle, it sits far below the mean. After inversion it lands far above the mean, growing closer to 1. All other amplitudes were slightly above the mean and therefore get pushed slightly below it.

The circuit

The diffusion operator can be written as $D = 2|s\rangle\langle s| - I$, where $|s\rangle = H^{\otimes n}|0\cdots 0\rangle$ is the uniform superposition. A standard decomposition for $n$ qubits conjugates a phase-flip of $|0\cdots 0\rangle$ by Hadamards:

$D = H^{\otimes n}\bigl(2|0\rangle\langle 0| - I\bigr)H^{\otimes n}.$

The inner operator $(2|0\rangle\langle 0| - I)$ flips every basis state except $|0\cdots 0\rangle$. Its circuit applies $X$ to every qubit (mapping $|0\cdots 0\rangle$ to $|1\cdots 1\rangle$), a controlled-$Z$ that phase-flips $|1\cdots 1\rangle$, then $X$ again to restore the other states. For 2 qubits the complete gate sequence is:

$H^{\otimes 2} \;\; X^{\otimes 2} \;\; CZ \;\; X^{\otimes 2} \;\; H^{\otimes 2}.$

Step-by-step for 2 qubits

Starting from the uniform superposition $|s\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$:

1. Open with $H^{\otimes 2}$ to rotate into the computational basis, mapping $|s\rangle \to |00\rangle$.
2. $X^{\otimes 2}$ flips both qubits: $|00\rangle \to |11\rangle$.
3. $CZ$ phase-flips $|11\rangle$ by $-1$.
4. $X^{\otimes 2}$ restores: $|11\rangle \to |00\rangle$, and all other states return to what they were before step 2 (each having picked up the sign applied in step 3 or not).
5. Close with $H^{\otimes 2}$ to return to the Hadamard basis.

The net effect on any amplitude vector is exactly the inversion-about-mean map.

Try it

Build the 2-qubit diffuser. The starter code applies the opening $H^{\otimes 2}$; your job is to complete the circuit with $X^{\otimes 2}$, $CZ$, $X^{\otimes 2}$, and the closing $H^{\otimes 2}$. The grader checks the full unitary matrix, so the circuit must match the exact operator $D$.

Sign in on the full site to ask questions and join the discussion.