Quantum Fourier Transform

The Quantum Fourier Transform on $n$ qubits ($N=2^n$ basis states) is the unitary

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

Unlike the classical discrete Fourier transform, which returns a full length-$N$ output vector, the QFT acts on the amplitudes of an $n$-qubit register and its output can only be sampled through measurement — it is a resource for building algorithms, not a way to read out a classical spectrum for free.

Circuit structure. The standard decomposition applies, for each qubit $j$ (most significant first), a Hadamard followed by controlled phase gates $R_k=\mathrm{diag}(1,e^{2\pi i/2^k})$ controlled by the less significant qubits, and finishes with a reversal of qubit order (implemented as $\lfloor n/2\rfloor$ SWAPs, or by relabeling wires in software). This gives exactly $n$ Hadamards and $n(n-1)/2$ controlled-phase gates: $O(n^2)$ gates total. Coppersmith's approximate QFT drops controlled rotations with angle smaller than $2\pi/2^m$ for a cutoff $m$, reducing the gate count to $O(n\log n)$ while introducing only exponentially small error for many downstream uses (period finding, phase estimation).

Small worked instance. Take $n=3$ ($N=8$) and the input $|j=0\rangle = |000\rangle$. Every phase factor $e^{2\pi i \cdot 0 \cdot k/8}=1$, so

$$\mathrm{QFT}_8|000\rangle = \frac{1}{\sqrt8}\sum_{k=0}^{7}|k\rangle,$$

exactly the state produced by applying $H$ to each of the three qubits independently — a directly checkable identity, since no controlled phase can fire when every control qubit is $|0\rangle$. For $j=1$, $\mathrm{QFT}_8|001\rangle=\frac{1}{\sqrt8}\sum_k e^{2\pi i k/8}|k\rangle$, i.e. the amplitudes trace out the eight 8th roots of unity in order — exactly the classical DFT of a Kronecker delta at index 1.

Where it is used. The QFT (or its inverse) is the last step of quantum phase estimation, the core of Shor's period-finding routine, and a building block for quantum arithmetic and some Hamiltonian-simulation schemes.