Using the QFT to Find Periods

In Shor's algorithm the quantum computer does not measure a period directly. Instead it produces a counting register whose amplitudes concentrate at integer multiples of $N/r$ , where $N = 2^n$ is the register size and $r$ is the unknown period. The inverse QFT maps those frequency peaks back into a pattern from which $r$ can be read.

From frequency peaks to period

After the oracle and the forward QFT, the counting register holds a superposition over the frequency values $k = 0, N/r, 2N/r, \ldots, (r-1) \cdot N/r$ . For a period-2 function in an $N = 8$ space the two peaks are at $k = 0$ and $k = 4$ :

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

Applying the inverse QFT to $|\Phi\rangle$ reverses the transform and recovers the original time-domain periodicity. The calculation proceeds as follows. The 3-qubit IQFT maps each basis state as

\mathrm{IQFT}\,|k\rangle = \frac{1}{2\sqrt{2}} \sum_{j=0}^{7} e^{-2\pi i\,jk/8}\,|j\rangle,

\mathrm{IQFT}\,|\Phi\rangle = \frac{1}{4} \sum_{j=0}^{7} \bigl(1 + e^{-i\pi j}\bigr)\,|j\rangle = \frac{1}{4} \sum_{j=0}^{7} \bigl(1 + (-1)^j\bigr)\,|j\rangle.

The factor $(1 + (-1)^j)$ equals 2 for even $j$ and 0 for odd $j$ , so all probability collapses onto the even outcomes:

\mathrm{IQFT}\,|\Phi\rangle = \frac{1}{2}\bigl(|0\rangle + |2\rangle + |4\rangle + |6\rangle\bigr).

Measuring yields each of $0, 2, 4, 6$ with probability $\tfrac{1}{4}$ . Every result is even — the GCD of any non-zero result and $N = 8$ is at least 2, immediately revealing the period.

The period-extraction recipe

In a complete Shor's-algorithm run the classical post-processing step applies continued fractions to a single measurement outcome $k$ : the best rational approximation to $k/N$ with denominator at most $N$ gives $s/r$ for some coprime pair $(s, r)$ , from which $r$ is extracted. For the case above, the QFT output state is $\frac{1}{\sqrt{2}}(|0\rangle + |4\rangle)$ , so the only non-trivial measurement outcome is $k = 4$ : $k/N = 4/8 = 1/2 = s/r$ , giving $r = 2$ directly in a single shot. For general $r$ the QFT peaks are at $k = j \cdot N/r$ for $j = 0, 1, \ldots, r-1$ ; continued fractions applied to each non-trivial outcome yields a candidate denominator, and taking the LCM of all candidates across several shots recovers the true period with high probability.

The 3-qubit inverse QFT circuit

Recall that the 3-qubit forward QFT (qubit 0 most significant) ends with a bit-reversal SWAP. Its inverse therefore begins with that same SWAP, then applies the reversed-and-conjugated rotation sequence:

| Step | Gate | Purpose | |------|------|---------| | 1 | $\mathrm{SWAP}(q_0, q_2)$ | undo the bit-reversal of the forward QFT | | 2 | $H(q_2)$ | undo coarsest Hadamard | | 3 | $CP(-\pi/2),\;\mathrm{ctrl}=q_1,\;\mathrm{tgt}=q_2$ | negate and reverse phase rotation | | 4 | $H(q_1)$ | undo middle Hadamard | | 5 | $CP(-\pi/4),\;\mathrm{ctrl}=q_0,\;\mathrm{tgt}=q_2$ | negate and reverse | | 6 | $CP(-\pi/2),\;\mathrm{ctrl}=q_0,\;\mathrm{tgt}=q_1$ | negate and reverse | | 7 | $H(q_0)$ | undo finest Hadamard |

Try it

The starter code prepares the frequency-domain state $\frac{1}{\sqrt{2}}(|0\rangle + |4\rangle)$ with a single Hadamard on qubit 0. Apply the 3-qubit inverse QFT and measure. The grader checks the output distribution, which should show equal probability on each even outcome $\{0, 2, 4, 6\}$ .

Run your code to see the quantum state.

After running, open the Probabilities tab. You should see four equal bars at positions 0, 2, 4, and 6 — every outcome is even, and the uniform spacing of $r = 2$ is directly readable from the measurement results. This is the moment where the inverse QFT converts an abstract frequency superposition into actionable period information.