QFT on Periodic States

The quantum Fourier transform is far more than a clever circuit: it is the key that unlocks periodicity hidden inside a quantum state. Whenever amplitudes repeat with period $r$ in a register of size $N = 2^n$ , the QFT concentrates all measurement probability on the multiples of $N/r$ . This "periodicity detection" is the engine of Shor's factoring algorithm and quantum phase estimation.

Periodic states

Call a state $r$ -periodic in an $n$ -qubit register if its amplitudes satisfy $f(j + r) = f(j)$ for all $j$ , with $r | N$ . A simple example for $n = 3$ ( $N = 8$ ) and $r = 2$ is the uniform superposition over even computational-basis states:

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

The amplitudes are $+\tfrac{1}{2}$ at $j = 0, 2, 4, 6$ and zero at $j = 1, 3, 5, 7$ — a period-2 pattern in an 8-element register.

This state is easy to prepare: qubits 0 and 1 each get a Hadamard (creating $|+\rangle$ ) while qubit 2 stays at $|0\rangle$ , giving $|+\rangle \otimes |+\rangle \otimes |0\rangle$ . The tensor product expands to exactly $\tfrac{1}{2}(|000\rangle + |010\rangle + |100\rangle + |110\rangle) = \tfrac{1}{2}(|0\rangle + |2\rangle + |4\rangle + |6\rangle)$ when qubit 0 is the most significant bit.

What the QFT does to a periodic state

The QFT maps $|j\rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i jk/N}|k\rangle$ . Applying this linearly to $|\psi\rangle$ and switching the order of summation:

\text{QFT}\,|\psi\rangle = \frac{1}{2}\sum_{m=0}^{3} \frac{1}{2\sqrt{2}}\sum_{k=0}^{7} e^{2\pi i (2m)k/8}|k\rangle = \frac{1}{4\sqrt{2}}\sum_{k=0}^{7}\underbrace{\left(\sum_{m=0}^{3} e^{2\pi i mk/4}\right)}_{\text{inner sum}}|k\rangle.

The inner sum is a geometric series in $e^{2\pi i k/4}$ . It equals 4 whenever $k \equiv 0 \pmod{4}$ and 0 otherwise (the complex phases cancel for all other $k$ ). So:

\text{QFT}\,|\psi\rangle = \frac{4}{4\sqrt{2}}\bigl(|0\rangle + |4\rangle\bigr) = \frac{1}{\sqrt{2}}\bigl(|0\rangle + |4\rangle\bigr).

Measuring yields $|0\rangle$ or $|4\rangle$ each with probability $\tfrac{1}{2}$ . Both outcomes are multiples of $N/r = 8/2 = 4$ — the spacing in frequency space that corresponds to the spacing $r = 2$ in the original state.

The 3-qubit QFT circuit (with bit reversal)

The standard circuit for the 3-qubit QFT proceeds qubit by qubit and ends with a SWAP to correct the output bit order (because the product-form derivation builds qubits in reversed order):

$H(q_0)$ , then $CP(\pi/2)$ with control $q_1$ , target $q_0$ , then $CP(\pi/4)$ with control $q_2$ , target $q_0$ .
$H(q_1)$ , then $CP(\pi/2)$ with control $q_2$ , target $q_1$ .
$H(q_2)$ .
$\text{SWAP}(q_0, q_2)$ to restore standard bit order.

Without the SWAP the circuit still implements a valid unitary (the bit-reversed QFT), but the output frequencies appear at permuted positions. Including the SWAP ensures that the outcome $k = 4$ is reported as the binary string 100, and $k = 0$ as 000 — exactly the results the calculation above predicts.

Try it

The starter code prepares the period-2 state and contains the QFT rotation steps. Add the final SWAP and the measurement. The grader checks the output distribution: it should place roughly 50% of probability on 000 and 50% on 100.

Run your code to see the quantum state.

After running, open the Probabilities tab. You will see two equal bars at positions 0 and 4 — every other outcome has probability zero. That is the QFT's periodicity fingerprint: a state with $r = 2$ in an $N = 8$ space maps to peaks spaced exactly $N/r = 4$ apart in frequency space.