Capstone: Design an Algorithm Demo

You have now studied the Quantum Fourier Transform, Grover's search, phase estimation, and benchmarking. A capstone project does not simply run one of these algorithms in isolation — it asks you to select the right tool and wire it together correctly for a concrete goal.

In this capstone you design a complete Grover search demo for a marked state of your choosing. Along the way you will see that the two principal ingredients — the oracle and the diffuser — compose cleanly regardless of which state is marked, as long as the oracle is constructed correctly.

What makes a good algorithm demo

A convincing algorithm demo has three properties:

Correctness — the output distribution concentrates on the answer with the theoretically predicted probability.
Transparency — every gate has a reason; a reader can trace why each step is necessary.
Generalisability — the structure extends to larger instances, even if the demo itself is small.

Grover's algorithm on two qubits satisfies all three. For $N = 4$ computational basis states with one marked state, the theoretical success probability after one iteration is

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

Exactly 100 % of the probability lands on the marked state.

Changing which state is marked

Every Grover circuit starts with the same diffuser. What changes is the oracle — the phase-kickback unitary $U_f$ that multiplies the marked state $|m\rangle$ by $-1$ and leaves all other states unchanged.

The general recipe for building an oracle that marks $|m\rangle = |m_1 m_0\rangle$ with a two-qubit CZ:

CZ applies $-1$ only when both control and target are in state $|1\rangle$ .
For each qubit $i$ where $m_i = 0$ , conjugate with $X$ so that qubit $i$ is flipped to $|1\rangle$ exactly when the input bit is $0$ .

For $|m\rangle = |10\rangle$ (qubit 0 is 1, qubit 1 is 0):

$U_{|10\rangle} = (I \otimes X)\;CZ\;(I \otimes X).$

The $X$ gates on qubit 1 ensure the CZ fires when qubit 0 is $|1\rangle$ and qubit 1 is $|0\rangle$ , which is precisely the $|10\rangle$ state.

The Grover diffuser, revisited

The diffuser implements a reflection about the uniform superposition $|s\rangle$ . Written as a unitary,

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

where $|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}$ . Because $H^{\otimes n}$ maps $|0\rangle^{\otimes n}$ to $|s\rangle$ , conjugating by $H^{\otimes n}$ converts the reflection about $|s\rangle$ into a reflection about $|0\rangle^{\otimes n}$ :

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

The inner operator $2|0^n\rangle\langle 0^n| - I$ is a controlled phase flip on the all-zeros state, which is built from $X^{\otimes n}$ , a multi-controlled- $Z$ , and $X^{\otimes n}$ again — the same pattern as the oracle, but always targeting $|00\ldots 0\rangle$ .

Putting it together

A complete one-iteration Grover demo for marking $|10\rangle$ on two qubits:

| Layer | Gates | Purpose | |-------|-------|---------| | Superposition | $H_0,\,H_1$ | Start from $|s\rangle$ | | Oracle | $X_1,\;CZ_{01},\;X_1$ | Phase-flip $|10\rangle$ | | Diffuser | $H_0 H_1,\;X_0 X_1,\;CZ_{01},\;X_0 X_1,\;H_0 H_1$ | Reflect about $|s\rangle$ |

Total: 14 gates. The result: all probability on $|10\rangle$ .

Try it

Complete the circuit by filling in all three layers. The grader checks the output distribution — it must place all probability on the $|10\rangle$ outcome.

Run your code to see the quantum state.

Once you pass the grader, reflect on the structure: the diffuser was identical to the one used in the $|11\rangle$ demo earlier in this module — only the oracle changed. That is the power of composable algorithm primitives.