Project: Benchmark Grover

Grover's algorithm is not just a one-shot circuit — it is a loop. You apply an oracle-then-diffuser block $k$ times, and the success probability oscillates with $k$ . Knowing where the peak is and confirming it experimentally is the first step in benchmarking any quantum search.

How success probability varies with iterations

For a search space of $N = 2^n$ items with exactly one marked item, the probability of finding that item after $k$ Grover iterations is

$P(k) = \sin^2\!\!\left(\,(2k+1)\,\theta\,\right), \qquad \theta = \arcsin\!\left(\frac{1}{\sqrt{N}}\right).$

The circuit rotates the initial equal superposition toward the marked state by $2\theta$ each iteration. After $k^* = \bigl\lfloor \tfrac{\pi}{4\theta} \bigr\rfloor$ iterations the state is as close to the marked item as the rotation can take it.

For $n = 2$ (four computational basis states, $N = 4$ ):

$\theta = \arcsin\!\left(\frac{1}{2}\right) = \frac{\pi}{6}.$

The probability after $k$ iterations is therefore

$P(k) = \sin^2\!\!\left(\frac{(2k+1)\pi}{6}\right).$

| $k$ | $(2k+1)\pi/6$ | $P(k)$ | |-----|--------------|--------| | 0 | $\pi/6$ | $0.25$ | | 1 | $\pi/2$ | $1.00$ | | 2 | $5\pi/6$ | $0.25$ | | 3 | $7\pi/6$ | $0.25$ |

The algorithm peaks at $k = 1$ with certainty and then falls back — running too many iterations is worse than running too few. A benchmark must find this peak.

Circuit structure for two qubits

A single Grover iteration on $n = 2$ consists of:

Superposition layer — apply $H^{\otimes 2}$ to start from the uniform state $|s\rangle = \tfrac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ .
Oracle — the phase-kickback oracle for the marked state $|11\rangle$ is a controlled- $Z$ : $CZ\,|11\rangle = -|11\rangle$ , leaving all other states unchanged.
Grover diffuser — reflection about $|s\rangle$ , implemented as $H^{\otimes 2}\,X^{\otimes 2}\,CZ\,X^{\otimes 2}\,H^{\otimes 2}$ .

The diffuser sandwiches the "flip about zero" operation between two changes of basis. In the $|s\rangle$ basis "flip about zero" maps every amplitude $a_i$ to $-a_i$ except $a_s$ , which stays positive, producing the mean-inversion that amplifies the oracle-marked state.

Try it

Complete the circuit by adding the oracle and the diffuser. The grader measures the output distribution — all probability should land on $|11\rangle$ (the "11" outcome) after exactly one optimal iteration.

Run your code to see the quantum state.

After grading, try mentally replacing the one-iteration structure with two iterations: the table above predicts $P(2) = 0.25$ , identical to the zero-iteration baseline. That is the overshoot phenomenon every Grover benchmark must guard against.