The Quantum Fourier Transform on Three Qubits

Trace the QFT gate by gate on three qubits, showing the Hadamard-and-controlled-phase ladder and the final qubit swap.

What the QFT does

The QFT maps a computational basis state |x> to a superposition with phases exp(2 pi i x k / N). It is the quantum analogue of the discrete Fourier transform and the engine inside phase estimation and Shor's algorithm.

Gate sequence

For three qubits (most significant first) the circuit is: H on q0; controlled-S from q1 to q0; controlled-T from q2 to q0; H on q1; controlled-S from q2 to q1; H on q2; then swap q0 and q2. S applies phase pi/2, T applies pi/4.

• H creates the superposition on each qubit.
• Controlled-phase gates inject the relative phases between qubits.
• The final swap reverses qubit order because the QFT naturally outputs bits in reverse.

import numpy as np
N=8
F=np.array([[np.exp(2j*np.pi*j*k/N) for k in range(N)] for j in range(N)])/np.sqrt(N)
x=3; psi=np.zeros(N,complex); psi[x]=1
out=F@psi
print(np.round(out,3))   # equal magnitude 1/sqrt(8), phases step by 2pi*3/8

Reading the output

For an input basis state the QFT output has uniform magnitude 1/sqrt(8) across all eight amplitudes; the information lives entirely in the phases, which wind at a rate set by x. That is why the inverse QFT in phase estimation can read a frequency off the register.

Cost

The QFT on n qubits uses n Hadamards and n(n-1)/2 controlled-phase gates - order n^2 gates, versus n*2^n for the classical FFT on the same amplitude vector. The speedup is real but only usable when the answer you want is itself a measurement of the transformed state.