Project: Build a QFT Library

Real quantum programs reuse sub-circuits the way classical programs reuse functions. The Quantum Fourier Transform (QFT) is the canonical example: it appears inside phase estimation, Shor's algorithm, and quantum arithmetic as a black-box subroutine. In this project you package a correct, self-contained QFT routine that can be dropped into any larger circuit.

Recap: what the QFT does

The $n$ -qubit QFT is the unitary defined by its action on every basis state $|j\rangle$ :

\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.

This is the discrete Fourier transform of the unit vector with a $1$ at position $j$ . It maps computational-basis states to uniform superpositions with relative phases that encode the Fourier frequencies of $j$ .

The product-state representation

The key to an efficient circuit is the product representation. Writing $j$ in binary as $j = j_{n-1} 2^{n-1} + \cdots + j_0$ , the QFT output factors as

\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 $0.j_{n-1-k}\cdots j_0$ is a binary fraction equal to $j / 2^{n-k}$ reduced modulo 1. Each output qubit is in a single-qubit superposition whose phase depends on only a few bits of $j$ .

This factored form dictates the circuit structure directly: qubit $k$ can be prepared independently by a Hadamard (which creates the $|0\rangle + e^{i\pi j_{n-1-k}}|1\rangle$ factor) followed by controlled-phase gates that contribute the remaining fractional bits.

The reusable circuit pattern

For $n$ qubits, label them $q_0$ (most significant) through $q_{n-1}$ (least significant). The QFT without bit-reversal SWAPs is built by the following loop:

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

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

For $n = 3$ this expands to exactly six gates:

| Step | Gate | Control | Target | Angle | |------|------|---------|--------|-------| | $k=0$ | $H$ | — | $q_0$ | — | | $k=0, j=1$ | $CP$ | $q_0$ | $q_1$ | $\pi/2$ | | $k=0, j=2$ | $CP$ | $q_0$ | $q_2$ | $\pi/4$ | | $k=1$ | $H$ | — | $q_1$ | — | | $k=1, j=1$ | $CP$ | $q_1$ | $q_2$ | $\pi/2$ | | $k=2$ | $H$ | — | $q_2$ | — |

Gate count and scalability

The loop above uses $n$ Hadamards and

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

controlled-phase gates, giving $\dfrac{n(n+1)}{2}$ gates in total — $O(n^2)$ in the circuit depth. A classical FFT on the same $N = 2^n$ -point input requires $O(N \log N) = O(n \cdot 2^n)$ arithmetic operations, which is exponentially more than the $O(n^2)$ gate count here (though the quantum circuit must still be read out, which collapses the superposition).

Why packaging matters

A reusable QFT routine means:

Correctness by construction. You verify the unitary once; every caller inherits the proof.
Easy composition. Phase estimation needs $\mathrm{QFT}^\dagger$ immediately after a controlled-unitary block. If the QFT is a function, swapping it for its adjoint is one line.
Benchmarking. Module 15 uses the QFT subroutine as a calibration target: its known gate count and unitary let you measure compiler overhead and simulator accuracy.

Try it

The starter code completes the blocks for $q_0$ and $q_2$ but leaves the controlled-phase gate for $q_1$ as a TODO. Add the missing gate to produce the correct 3-qubit QFT unitary. The grader checks the full unitary matrix, so a missing or wrong gate will fail.

Run your code to see the quantum state.