Multiple Marked Items

So far you have seen Grover's algorithm with exactly one marked item. The algorithm generalises to $M$ marked items, and understanding that generalisation reveals why Grover is fast and how fewer iterations are needed when more solutions exist.

Geometry with $M$ solutions

Grover's algorithm is best understood geometrically. Let $N = 2^n$ be the total number of basis states and $M$ the number of marked items. Define two unit vectors:

$|W\rangle = \frac{1}{\sqrt{M}}\sum_{x \in \text{marked}} |x\rangle, \qquad |W^\perp\rangle = \frac{1}{\sqrt{N-M}}\sum_{x \notin \text{marked}} |x\rangle.$

The initial uniform superposition $|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}$ lies in the plane spanned by $|W\rangle$ and $|W^\perp\rangle$:

$|s\rangle = \sqrt{\frac{M}{N}}\,|W\rangle + \sqrt{\frac{N-M}{N}}\,|W^\perp\rangle.$

The angle $\theta$ between $|s\rangle$ and $|W^\perp\rangle$ satisfies $\sin\theta = \sqrt{M/N}$.

Each Grover iteration is a rotation by $2\theta$ toward $|W\rangle$. After $k$ iterations the total probability of measuring any marked item is

$P_{\text{marked}}(k) = \sin^2\!\bigl((2k+1)\theta\bigr).$

The optimal number of iterations

Setting $P_{\text{marked}} = 1$ requires $(2k+1)\theta = \pi/2$, giving

$k^* = \frac{\pi/2 - \theta}{2\theta} = \frac{\pi}{4\theta} - \frac{1}{2}.$

For small $\theta$ this is approximately $\pi/(4\theta) \approx \tfrac{\pi}{4}\sqrt{N/M}$.

A special case: exact certainty

For $N = 8$ (three qubits) and $M = 2$, we get $\sin\theta = \sqrt{2/8} = 1/2$, so $\theta = \pi/6$. The optimal number of iterations is

$k^* = \frac{\pi/2 - \pi/6}{2 \cdot \pi/6} = \frac{\pi/3}{{\pi/3}} = 1.$

Exactly one iteration, and the success probability is $\sin^2(3 \cdot \pi/6) = \sin^2(\pi/2) = 1$. This is not an approximation: the geometry works out perfectly for $M = 2$ in an 8-element space.

The multi-target oracle

When the oracle must mark multiple states $\{x_1, x_2, \ldots, x_M\}$, you simply compose the individual phase-flip unitaries:

$U_f = U_{x_M} \cdots U_{x_2} \cdot U_{x_1}$

where $U_{x_i}$ phase-flips only $|x_i\rangle$. The diffuser stays unchanged — it reflects about the uniform superposition $|s\rangle$ regardless of how many items the oracle marks.

Each single-target oracle is built with the same pattern you already know: apply $X$ gates to every qubit that should be $|0\rangle$ in the target bitstring (converting the target to all-ones), then apply an $n$-qubit controlled-$Z$, then undo the $X$ gates. The $n$-qubit controlled-$Z$ is realised without ancilla qubits by the identity

$\text{C}^{n-1}Z = H_{n-1} \cdot \text{C}^{n-1}X \cdot H_{n-1},$

i.e., sandwich a Toffoli (or its multi-controlled generalisation) between Hadamards on the last qubit. For three qubits this is $H(2),\, \text{CCX}(0,1,2),\, H(2)$.

Try it

The exercise targets $N = 8$ states with $M = 2$ marked items: $|000\rangle$ and $|111\rangle$. Complete the two oracle phase-flips; the diffuser is already provided. The grader checks the output distribution, which should place equal probability on $|000\rangle$ and $|111\rangle$ and zero on all other states.

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