The QFT Defined

The quantum Fourier transform (QFT) is the quantum analogue of the discrete Fourier transform (DFT). It is one of the most important subroutines in quantum computing, underpinning Shor's factoring algorithm and quantum phase estimation.

The Definition

For an $n$ -qubit system with $N = 2^n$ states, the QFT maps each computational basis state $|j\rangle$ to

\text{QFT}\,|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i\, jk/N}\, |k\rangle.

This looks exactly like the DFT — the $j$ -th input becomes a uniform superposition whose $k$ -th amplitude is the complex exponential $e^{2\pi i\, jk/N}$ . The difference is that the QFT acts on a quantum state and produces a quantum state; it uses quantum parallelism to handle all $N$ inputs simultaneously.

Because every amplitude has the same magnitude $1/\sqrt{N}$ , the QFT does not change measurement probabilities for basis states — the encoding is entirely in the phases.

Product Representation

The summation formula can be rewritten as a tensor product over individual qubits. Writing $j$ in binary as $j = j_{n-1} 2^{n-1} + \cdots + j_1 2 + j_0$ , the QFT output is

\text{QFT}\,|j\rangle = \frac{1}{\sqrt{N}} \bigl(|0\rangle + e^{2\pi i\, 0.j_0}\,|1\rangle\bigr) \otimes \bigl(|0\rangle + e^{2\pi i\, 0.j_1 j_0}\,|1\rangle\bigr) \otimes \cdots \otimes \bigl(|0\rangle + e^{2\pi i\, 0.j_{n-1}\cdots j_0}\,|1\rangle\bigr),

where $0.j_k\cdots j_0$ is the binary fraction $j_k/2 + \cdots + j_0/2^{k+1}$ .

This product form reveals the circuit structure: each qubit in the output needs a Hadamard (to create the $|0\rangle + e^{i\phi}|1\rangle$ superposition) followed by controlled-phase rotations that encode the appropriate binary fraction.

The Two-Qubit Circuit

For $n = 2$ (so $N = 4$ ), the product form gives

\text{QFT}\,|j\rangle = \frac{1}{2} \bigl(|0\rangle + e^{2\pi i\, j/2}\,|1\rangle\bigr) \otimes \bigl(|0\rangle + e^{2\pi i\, j/4}\,|1\rangle\bigr).

The circuit that implements this (with qubit 0 as the most significant bit) has four steps:

H on qubit 0 — creates the superposition $|0\rangle + e^{2\pi i\, j_1 / 2}\,|1\rangle$ on the top qubit, which already carries the coarser phase.
Controlled-phase CP( $\pi/2$ ) with control = qubit 1, target = qubit 0 — adds the additional phase $e^{i\pi j_0/2}$ to the $|1\rangle$ component of qubit 0, building the full binary fraction $0.j_1 j_0$ .
H on qubit 1 — transforms the second qubit into its own Fourier superposition.
SWAP(0, 1) — reverses the output bit order so the result matches the standard QFT ordering (most significant output qubit first).

The controlled-phase gate $CP(\lambda)$ applies the phase $e^{i\lambda}$ to the $|11\rangle$ component. For step 2, $\lambda = \pi/2$ so the accumulated phase on the $|1\rangle$ branch of qubit 0 is $e^{i\pi j_0 / 2}$ , which is $e^{2\pi i\, (0.j_1 j_0)}$ combined with the Hadamard contribution — precisely the required value.

The full circuit requires only $O(n^2)$ gates for $n$ qubits, compared with $O(N \log N)$ operations for the classical FFT (where $N = 2^n$ ), yielding an exponential speed-up for the Fourier subroutine itself.

Try it

Build the 2-qubit QFT. The grader checks the full unitary matrix of your circuit against the exact QFT matrix, so the circuit must be completely correct — a partial or empty circuit will fail.

Run your code to see the quantum state.