Controlled Rotations in the QFT

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

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

The single-qubit case (previous lesson) reduces to a Hadamard. For more qubits the circuit needs controlled phase gates to encode the finer frequency components.

The controlled phase gate

The controlled- $P(\lambda)$ gate (written $CP(\lambda)$ ) acts on a control qubit $c$ and a target qubit $t$ :

CP(\lambda) = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^{i\lambda} \end{pmatrix}

in the $\{|00\rangle, |01\rangle, |10\rangle, |11\rangle\}$ basis. It does nothing unless both qubits are $|1\rangle$ , in which case it multiplies the amplitude by $e^{i\lambda}$ . No control, no rotation — this conditional action is what makes the QFT constructive.

The QFT uses a family of these gates with angles $\lambda_k = \pi / 2^{k-1}$ . In traditional notation these are called $R_k$ gates:

R_k = CP\!\left(\frac{\pi}{2^{k-1}}\right), \qquad k = 1, 2, 3, \ldots

So $R_1 = CP(\pi)$ (a controlled- $Z$ ), $R_2 = CP(\pi/2)$ , $R_3 = CP(\pi/4)$ , and so on.

The 3-qubit QFT circuit

For $n = 3$ qubits (labeled $q_0, q_1, q_2$ from most to least significant) the QFT circuit reads:

$H(q_0)$ , then $CP(\pi/2)$ with control $q_0$ , target $q_1$ , then $CP(\pi/4)$ with control $q_0$ , target $q_2$ .
$H(q_1)$ , then $CP(\pi/2)$ with control $q_1$ , target $q_2$ .
$H(q_2)$ .

The pattern is systematic: each qubit first gets a Hadamard, then acts as the control for successively finer phase kicks to the less-significant qubits. The angle halves with each step because the target qubit sits one position further down the binary fraction.

Gate count

The $n$ -qubit QFT uses exactly $n$ Hadamards and $n(n-1)/2$ controlled-phase gates — a total of $O(n^2)$ gates. This is exponentially fewer than the $O(n \cdot 2^n)$ operations needed by the classical FFT on the same $2^n$ -point input.

For $n = 3$ : 3 Hadamards and $3 \cdot 2 / 2 = 3$ controlled-phase gates, for 6 gates total.

Try it

The starter code gives you the first qubit's block and the Hadamard for qubit 1. Add the missing controlled-phase rotation for qubit 1. The grader checks the full unitary matrix, so leaving the circuit incomplete will fail.

Run your code to see the quantum state.