Three-Qubit Grover

Scaling Grover's algorithm from 2 to 3 qubits takes us from $N = 4$ to $N = 8$ items and introduces the first non-trivial question: how many iterations do we need?

Optimal iteration count for eight items

The geometric analysis (see the Optimal Number of Iterations lesson) gives

t^* = \left\lfloor \frac{\pi}{4}\sqrt{\frac{N}{M}} \right\rfloor,

where $M$ is the number of marked items. With $N = 8$ , $M = 1$ :

\sin\theta = \sqrt{\frac{1}{8}}, \qquad t^* = \left\lfloor \frac{\pi}{4}\sqrt{8} \right\rfloor = \left\lfloor \frac{\pi\sqrt{2}}{2} \right\rfloor = \lfloor 2.22 \rfloor = 2.

Two iterations push the success probability to

P_{\text{success}} = \sin^2\!\bigl((2\cdot 2 + 1)\theta\bigr) = \sin^2(5\theta) \approx 0.945.

That is close to — but not quite — certainty; $N = 8$ does not produce an exact multiple of $\pi/2$ the way $N = 4$ did. A third iteration would over-rotate and lower the probability.

Oracle for a three-qubit marked state

Suppose we want to mark $|101\rangle$ (qubit 0 is $|1\rangle$ , qubit 1 is $|0\rangle$ , qubit 2 is $|1\rangle$ ). The standard approach converts a phase-flip oracle for $|111\rangle$ into one for any target pattern by flipping the zero-valued qubits with $X$ before and after the core gate:

O_{|101\rangle} = (I \otimes X \otimes I)\; O_{|111\rangle}\; (I \otimes X \otimes I).

The $O_{|111\rangle}$ gate itself is a three-qubit controlled- $Z$ (CCZ). Because the circuit API provides CCX (Toffoli) rather than CCZ directly, we use the identity $CZ = (I \otimes H)\,CX\,(I \otimes H)$ , extended to three qubits:

\text{CCZ}(q_0,q_1,q_2) = H(q_2)\;\text{CCX}(q_0,q_1,q_2)\;H(q_2).

So the full oracle for $|101\rangle$ is:

$X(q_1)$ — flip the zero qubit.
$H(q_2)$ , $\text{CCX}(0,1,2)$ , $H(q_2)$ — controlled-controlled- $Z$ .
$X(q_1)$ — undo the flip.

The three-qubit diffuser

The diffuser reflects amplitudes about their mean. For $n$ qubits the pattern is always:

H^{\otimes n}\; X^{\otimes n}\; \text{(zero-phaseflip)}\; X^{\otimes n}\; H^{\otimes n},

where the zero-phase-flip adds a $-1$ only to $|00\ldots0\rangle$ . For three qubits the zero-phase-flip is again a CCZ gate (all controls on $|1\rangle$ after the $X$ layer):

H(2)\;\text{CCX}(0,1,2)\;H(2).

Putting it together

One full Grover iteration is: oracle then diffuser. With two iterations the procedure is:

Apply $H^{\otimes 3}$ to create the uniform superposition $|s\rangle$ .
Apply oracle + diffuser (iteration 1).
Apply oracle + diffuser (iteration 2).
Measure — outcome $|101\rangle$ appears with probability $\approx 94.5\,\%$ .

Try it

The starter code provides the superposition and both diffuser blocks. Add the oracle for $|101\rangle$ in each iteration. The grader checks the output distribution: $|101\rangle$ (the 5th basis state in binary, index 5 counting from 0) must carry the dominant probability.

Run your code to see the quantum state.