Checkpoint: Build Grover Search

This is your Grover checkpoint. Instead of filling a partially written circuit, you build the full search algorithm from scratch for a chosen marked state. The goal is to show that you can assemble the oracle and diffuser for any target, not just the ones used in the worked examples.

Recap: the algorithm in three steps

For an $n$ -qubit search space of $N = 2^n$ items with one marked state $|x^*\rangle$ , the complete Grover algorithm is:

\;\xrightarrow{\;D\;}\; G|s\rangle \approx |x^*\rangle$$ 1. **Superposition.** Apply $H$ to every qubit to create the uniform superposition $|s\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$. 2. **Oracle $U_f$.** Phase-flip the marked state: $$U_f|x\rangle = (-1)^{f(x)}|x\rangle, \qquad f(x) = \begin{cases}1 & x = x^*\\0 & \text{otherwise}\end{cases}$$ The standard recipe for an arbitrary $|x^*\rangle$ is to flip the qubits where $x^*$ has a $0$ bit (with $X$ gates), apply an $n$-controlled-$Z$, then undo the $X$ flips. For two qubits the $n$-controlled-$Z$ is simply $CZ$. 3. **Diffuser $D$.** Reflect amplitudes about their mean: $$D = 2|s\rangle\langle s| - I = H^{\otimes n}\,X^{\otimes n}\,CZ\,X^{\otimes n}\,H^{\otimes n}.$$ Amplitudes above the mean grow; the marked amplitude — which was made negative by the oracle — grows the most. ## Why one iteration suffices for $N = 4$ For two qubits, $N = 4$. The initial angle between the state vector and the marked direction is $$\theta = \arcsin\!\left(\frac{1}{\sqrt{N}}\right) = \arcsin\!\left(\frac{1}{2}\right) = \frac{\pi}{6}.$$ Each Grover iteration rotates by $2\theta = \pi/3$ in the two-dimensional subspace spanned by $|x^*\rangle$ and the uniform superposition of unmarked states. After one iteration the total angle from the horizontal is $\theta + 2\theta = 3\theta = \pi/2$, which coincides exactly with $|x^*\rangle$. The probability of measuring the marked state becomes $\sin^2(\pi/2) = 1$ — perfect. <Callout type="tip"> For larger $N$ you need $\lfloor \tfrac{\pi}{4}\sqrt{N} \rfloor$ iterations. Two qubits happen to be the one case where a single iteration is exact (no over- or under-rotation). </Callout> ## Building the oracle for $|01\rangle$ The marked state here is $|01\rangle$: qubit 0 is $|0\rangle$, qubit 1 is $|1\rangle$ (recall that qubit 0 is the **most significant** bit). The oracle must flip the sign of this state only. The $CZ$ gate natively flips $|11\rangle$. To redirect it at $|01\rangle$, apply $X$ to qubit 0 beforehand (turning $|01\rangle \to |11\rangle$), fire $CZ$, then apply $X$ to qubit 0 again to restore the labels. Every other basis state passes through unchanged because at least one qubit remains $|0\rangle$ when $CZ$ acts. $$\text{oracle for }|01\rangle:\quad X_0 \cdot CZ_{01} \cdot X_0$$ ## Try it Implement the full algorithm: superposition, oracle for $|01\rangle$, then diffuser. The grader checks the output **probability distribution** — all weight must land on the bitstring `01`. <RunnableExample /> After a correct run you will see a single bar at `01` with probability $1$. That is Grover's quadratic speedup in its simplest, exact form.