Building the Two-Qubit QFT

The two-qubit QFT is the first case where controlled phase gates appear explicitly. Working through it by hand fixes the pattern used in all larger QFT circuits.

The QFT on two qubits

For $n = 2$ qubits ( $N = 4$ ) the general formula

\mathrm{QFT}_n|j\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i\,jk/2^n}|k\rangle

gives the four basis-state mappings:

\mathrm{QFT}_2|j\rangle = \frac{1}{2} \sum_{k=0}^{3} e^{2\pi i\,jk/4}|k\rangle, \qquad j = 0, 1, 2, 3.

Writing $j = 2j_0 + j_1$ (with $j_0, j_1 \in \{0,1\}$ the most- and least-significant bits) and $k = 2k_0 + k_1$ , the sum factors into a tensor product:

\mathrm{QFT}_2|j_0 j_1\rangle = \frac{1}{\sqrt{2}}\bigl(|0\rangle + e^{i\pi j_1}|1\rangle\bigr)_0 \otimes \frac{1}{\sqrt{2}}\bigl(|0\rangle + e^{i\pi j_0 + i\pi j_1/2}|1\rangle\bigr)_1,

where the subscript labels the qubit. Each qubit ends in a superposition, but the phase of its $|1\rangle$ component depends on the input bits. The phase on qubit 1 has two contributions: $e^{i\pi j_0}$ (from the more-significant bit) and $e^{i\pi j_1/2}$ (a finer half-turn from its own bit — together these encode the fractional binary expansion $0.j_0 j_1$ ).

The circuit

Three types of gate realize the factored product:

Hadamard on qubit 0 — creates $(|0\rangle + e^{i\pi j_0}|1\rangle)/\sqrt{2}$ on the most-significant qubit.
$R_2$ gate on qubit 1 — adds the $e^{i\pi j_0/2}$ phase to qubit 1's $|1\rangle$ component, conditional on qubit 0 being $|1\rangle$ . In circuit API notation this is $CP(\pi/2)$ with control qubit 0 and target qubit 1.
Hadamard on qubit 1 — creates the superposition $(|0\rangle + e^{i\pi j_1}|1\rangle)/\sqrt{2}$ on the least-significant qubit.
SWAP(0, 1) — reverses the output bit order to match the standard convention where the most-significant output sits in qubit 0.

The complete sequence is:

\mathrm{QFT}_2 = \mathrm{SWAP} \cdot (I \otimes H) \cdot CP(\pi/2) \cdot (H \otimes I)

(gates applied right-to-left in time, i.e. $H\otimes I$ acts first; standard matrix multiplication order).

Gate count and scaling

The two-qubit QFT uses 2 Hadamards, 1 controlled-phase gate, and 1 SWAP — 4 gates total. The general $n$ -qubit QFT uses $n$ Hadamards, $n(n-1)/2$ controlled-phase gates, and $\lfloor n/2 \rfloor$ SWAPs, for an $O(n^2)$ circuit. This compares favourably with the classical fast Fourier transform which needs $O(n \cdot 2^n)$ arithmetic operations on the same $2^n$ -point data.

Try it

The starter code has all four steps — only the $R_2$ controlled-phase rotation is missing. Add it between the two Hadamards. The grader checks the full unitary matrix, so an empty or incomplete circuit will fail.

Run your code to see the quantum state.