The General QFT Circuit

Previous lessons built the 2- and 3-qubit QFT one step at a time. Now we write down the general pattern that scales to any number of qubits $n$ .

The general circuit rule

Label the qubits $q_0, q_1, \ldots, q_{n-1}$ with $q_0$ being the most significant bit. The QFT circuit without bit-reversal SWAPs is constructed by the following loop:

For $k = 0, 1, \ldots, n-1$ :

Apply $H$ to qubit $k$ .
For $j = 1, 2, \ldots, n-1-k$ : apply $CP\!\left(\dfrac{\pi}{2^j}\right)$ with control qubit $k$ and target qubit $k + j$ .

That is all. For $n = 3$ this expands to:

$k = 0$ : $H(q_0)$ , $CP(\pi/2,\, q_0 \to q_1)$ , $CP(\pi/4,\, q_0 \to q_2)$ .
$k = 1$ : $H(q_1)$ , $CP(\pi/2,\, q_1 \to q_2)$ .
$k = 2$ : $H(q_2)$ — no controlled-phase gates because no later qubits exist.

Why it works

Recall the product representation of the QFT:

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

where $j = j_{n-1} 2^{n-1} + \cdots + j_0$ in binary and $0.j_{n-1}\cdots j_0 = j/2^n$ is a binary fraction. Output qubit $k$ must carry the phase $e^{2\pi i\, 0.j_{n-1-k}\cdots j_0}$ .

The Hadamard on $q_k$ creates the superposition $|0\rangle + e^{i\pi j_{n-1-k}}|1\rangle$ , which supplies the most-significant bit of the required binary fraction. Each subsequent $CP(\pi/2^j)$ gate — triggered only when both $q_k$ and $q_{k+j}$ are $|1\rangle$ — adds the phase $e^{i\pi j_{n-1-k-j}/2^j}$ , contributing the next binary fraction digit. After all $n-1-k$ controlled rotations, the output qubit $k$ carries exactly the right phase.

Gate count

The loop runs $n$ Hadamards and

$\sum_{k=0}^{n-1}(n-1-k) = \frac{n(n-1)}{2}$

controlled-phase gates, for a total of $\dfrac{n(n+1)}{2}$ gates. This is $O(n^2)$ , whereas the classical FFT on the same $N = 2^n$ -point input costs $O(N \log N) = O(n \cdot 2^n)$ operations — an exponential improvement in the Fourier subroutine itself.

Try it

The starter code completes qubits 0 and 1. Add the missing Hadamard for qubit 2 to finish the 3-qubit QFT. The grader checks the full unitary matrix, so an incomplete circuit will fail.

Run your code to see the quantum state.