Checkpoint: Period Finding

This checkpoint consolidates the entire Shor module. You will simulate the decisive quantum step of period finding: starting from the periodic superposition that emerges after measuring the output register, you apply the inverse Quantum Fourier Transform and observe that the measurement probabilities concentrate at integer multiples of $Q/r$ , directly revealing the period $r$ .

The setup

In a full execution of the period-finding subroutine (§4 of the prior lesson) the circuit produces, after measuring the ancilla register, an equally-spaced superposition in the input register. For a function with period $r = 2$ on an $n = 3$ -qubit ( $Q = 2^3 = 8$ ) register the surviving states are those $x$ with $a^x \equiv v \pmod{N}$ , spaced by $r = 2$ :

\frac{1}{\sqrt{4}}\bigl(|0\rangle + |2\rangle + |4\rangle + |6\rangle\bigr).

In binary (qubit 0 most significant): states $|000\rangle, |010\rangle, |100\rangle, |110\rangle$ . Qubit 2 is always $0$ ; qubits 0 and 1 range over all combinations. This is exactly the state produced by $H \otimes H \otimes I$ applied to $|000\rangle$ .

Why the inverse QFT reveals the period

The inverse QFT maps the equally-spaced superposition to a new superposition concentrated at integer multiples of $Q/r$ . For a uniform superposition over $M = Q/r$ equally-spaced inputs $\{0, r, 2r, \ldots, (M-1)r\}$ :

\mathrm{QFT}^\dagger \left(\frac{1}{\sqrt{M}}\sum_{k=0}^{M-1}|kr\rangle\right) = \frac{1}{\sqrt{r}}\sum_{j=0}^{r-1} \left|\frac{j \cdot Q}{r}\right\rangle.

For $r = 2$ and $Q = 8$ the two peaks are at $j \cdot 8 / 2 = 0$ and $4$ . Each has probability $1/r = 1/2$ , so measuring the input register returns $0$ or $4$ with equal probability. Dividing by $Q = 8$ gives the fraction $j/r \in \{0, 1/2\}$ ; continued-fraction expansion of $1/2$ immediately yields the denominator $r = 2$ .

The 3-qubit inverse QFT circuit

The forward 3-qubit QFT (as built in the module 2 checkpoint) is:

\text{QFT}_3 = \mathrm{SWAP}_{02} \cdot H_2 \cdot CP\!\left(\tfrac{\pi}{2}\right)_{2 \to 1} \cdot H_1 \cdot CP\!\left(\tfrac{\pi}{4}\right)_{2 \to 0} \cdot CP\!\left(\tfrac{\pi}{2}\right)_{1 \to 0} \cdot H_0.

Wait — the forward QFT is built left to right as: $H_0, CP(\pi/2)_{1\to 0}, CP(\pi/4)_{2\to 0}, H_1, CP(\pi/2)_{2\to 1}, H_2, \mathrm{SWAP}_{02}$ .

Its inverse $\mathrm{QFT}_3^\dagger$ reverses the gate order and takes the adjoint of each gate ( $H^\dagger = H$ , $CP(\lambda)^\dagger = CP(-\lambda)$ , $\mathrm{SWAP}^\dagger = \mathrm{SWAP}$ ):

\mathrm{QFT}_3^\dagger = H_0 \cdot CP\!\left(-\tfrac{\pi}{2}\right)_{1 \to 0} \cdot CP\!\left(-\tfrac{\pi}{4}\right)_{2 \to 0} \cdot H_1 \cdot CP\!\left(-\tfrac{\pi}{2}\right)_{2 \to 1} \cdot H_2 \cdot \mathrm{SWAP}_{02}.

Reading the circuit in application order (first to last):

$\mathrm{SWAP}(0, 2)$
$H(2)$
$CP(-\pi/2,\ 2,\ 1)$
$H(1)$
$CP(-\pi/4,\ 2,\ 0)$
$CP(-\pi/2,\ 1,\ 0)$
$H(0)$

Try it

The starter code already prepares the periodic superposition. Add the seven inverse-QFT gates. The grader checks the output distribution — it must place probability $1/2$ on state $|000\rangle$ (index 0) and $1/2$ on state $|100\rangle$ (index 4), exactly as the period-finding theory predicts.

Run your code to see the quantum state.