Checkpoint: Implement the QFT

This checkpoint asks you to assemble the complete 3-qubit QFT from scratch — Hadamards, controlled-phase rotations, and the final bit-reversal SWAPs. It consolidates everything covered in this module.

Recap: the product representation

The QFT maps any $n$ -qubit basis state $|j\rangle$ to

\mathrm{QFT}_n|j\rangle = \frac{1}{\sqrt{2^n}} \bigotimes_{k=0}^{n-1} \Bigl(|0\rangle + e^{2\pi i\, j / 2^{k+1}}\,|1\rangle\Bigr).

Each tensor factor depends only on a single binary fraction of $j$ , which is what makes an efficient circuit possible: a Hadamard creates the $|0\rangle + e^{i\phi}|1\rangle$ superposition, and controlled-phase gates $CP(\lambda)$ accumulate the remaining phase contributions from the more-significant (lower-indexed) qubits.

The 3-qubit circuit structure

Label the qubits $q_0$ (most significant), $q_1$ , $q_2$ (least significant). The algorithm proceeds in three stages:

Stage for $q_0$ : Apply $H(q_0)$ to start the Fourier superposition, then use $q_1$ and $q_2$ as controls to add the finer phase contributions. The angles are $\pi/2$ (from $q_1$ ) and $\pi/4$ (from $q_2$ ):

H(q_0),\quad CP\!\left(\tfrac{\pi}{2}\right)_{q_1 \to q_0},\quad CP\!\left(\tfrac{\pi}{4}\right)_{q_2 \to q_0}.

Stage for $q_1$ : Apply $H(q_1)$ , then one controlled-phase from $q_2$ with angle $\pi/2$ :

H(q_1),\quad CP\!\left(\tfrac{\pi}{2}\right)_{q_2 \to q_1}.

Stage for $q_2$ : Just a Hadamard:

H(q_2).

Bit reversal: The stages above leave the output in reversed bit order — $q_0$ holds the least significant Fourier frequency. A single SWAP between $q_0$ and $q_2$ restores the standard ordering where $q_0$ carries the most significant frequency.

Gate count

For $n = 3$ the circuit uses $n = 3$ Hadamards and $n(n-1)/2 = 3$ controlled-phase gates, for 6 gates total before the $\lfloor n/2 \rfloor = 1$ SWAP. In general the QFT uses $O(n^2)$ gates, compared with the $O(n \cdot 2^n)$ operations of a classical FFT on the same $2^n$ -point input.

Try it

Complete the circuit by adding the missing controlled-phase rotation. The grader checks the full unitary matrix of your 3-qubit circuit against the exact QFT unitary, so every gate must be correct — an incomplete or wrong circuit will fail.

Run your code to see the quantum state.