The Quantum Fourier Transform Circuit

Derivation

The Quantum Fourier Transform Circuit

D-413 Home PU-404 Threads waves · symmetry Depends on Universality of CNOT with Single-Qubit Gates

Statement

The quantum Fourier transform (QFT) on \(n\) qubits, defined on computational basis states \(\lvert j\rangle\) with \(j\in\{0,\dots,N-1\}\) and \(N=2^{n}\) by \(\lvert j\rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i jk/N}\lvert k\rangle\), factorises into a tensor product of single-qubit states, and this product is generated by exactly \(n\) Hadamard gates and \(\binom{n}{2}=\tfrac{n(n-1)}{2}\) two-qubit controlled-phase gates (plus a bit-reversal permutation), so the whole unitary is realised in \(O(n^{2})\) elementary gates.

Why it matters

The classical fast Fourier transform costs \(O(N\log N)=O(n\,2^{n})\) arithmetic operations on \(N=2^{n}\) amplitudes. The QFT performs the same unitary change of basis on a superposition of all \(N\) amplitudes using only \(O(n^{2})=O(\log^{2}N)\) gates — an exponential compression in the count of primitive operations. This is not a classical speedup for computing a Fourier transform of stored data (the amplitudes are not readable), but it is the engine inside quantum phase estimation and hence Shor's factoring and discrete-logarithm algorithms.

The construction is also a clean illustration of how a global, seemingly dense unitary (an \(N\times N\) matrix of phases) is secretly local: the phase \(e^{2\pi i jk/N}\) separates across output qubits, so entangling resources are needed only pairwise and only through controlled phases whose angles halve down the register.

Assumptions

The register holds exactly \(n\) qubits with \(N=2^{n}\).If \(N\) is not a power of two the tensor-product factorisation below fails term by term; one must pad to the next power of two or use an approximate QFT for the desired modulus, and the clean gate count no longer holds.

Basis states are ordered by binary place value, \(j=\sum_{m=1}^{n} j_m 2^{\,n-m}\) with \(j_m\in\{0,1\}\).If a different bit ordering is used the controlled-phase pattern and the final swap network change; drop the convention and the circuit still works but the wiring must be re-derived.

Gates act exactly (unitary, no decoherence, exact phase angles \(2\pi/2^{k}\)).Physical controlled-phase gates with angle \(2\pi/2^{k}\) become exponentially small for large \(k\); if these cannot be applied to the required precision the transform is only approximate, motivating the approximate QFT that discards small-angle gates. Dropped exactness turns an exact unitary into one with bounded operator-norm error.

Derivation

\[ \mathrm{QFT}\,\lvert j\rangle=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i jk/N}\,\lvert k\rangle,\qquad N=2^{n}. \]

Definition of the discrete Fourier transform lifted to amplitudes; unitarity follows from orthogonality of the characters \(e^{2\pi i jk/N}\). A

\[ k=\sum_{l=1}^{n} k_l\,2^{\,n-l}\ \Longrightarrow\ \frac{k}{N}=\sum_{l=1}^{n} k_l\,2^{-l}. \]

Write the output index in binary and divide by \(N=2^{n}\); each bit \(k_l\) carries a weight \(2^{-l}\). Pure change of variable. A

\[ e^{2\pi i j k/N}=\exp\!\Big(2\pi i j\sum_{l=1}^{n} k_l 2^{-l}\Big)=\prod_{l=1}^{n} e^{2\pi i j\,k_l 2^{-l}}. \]

The exponential of a sum is a product of exponentials; the phase separates over the output bits \(k_l\). This is the key factorisation. A

\[ \sum_{k=0}^{N-1}=\sum_{k_1=0}^{1}\sum_{k_2=0}^{1}\cdots\sum_{k_n=0}^{1},\qquad \lvert k\rangle=\lvert k_1\rangle\otimes\cdots\otimes\lvert k_n\rangle. \]

Summing over all \(k\) is summing independently over each bit; the basis ket factorises across qubits. Distributivity of \(\otimes\) over \(+\). B

\[ \mathrm{QFT}\,\lvert j\rangle=\frac{1}{\sqrt{N}}\bigotimes_{l=1}^{n}\ \sum_{k_l=0}^{1} e^{2\pi i j\,k_l 2^{-l}}\lvert k_l\rangle =\frac{1}{\sqrt{N}}\bigotimes_{l=1}^{n}\Big(\lvert 0\rangle+e^{2\pi i j\,2^{-l}}\lvert 1\rangle\Big). \]

Interchange the product over \(l\) with the sums over \(k_l\) (each factor depends on a single bit), then evaluate the two-term sum. This is the product (unentangled) form of the QFT output. C

\[ j\,2^{-l}=\sum_{m=1}^{n} j_m 2^{\,n-m-l}. \]

Insert the binary expansion of the input \(j\). The integer part of this number contributes a phase \(e^{2\pi i (\text{integer})}=1\) and can be dropped. B

\[ e^{2\pi i j\,2^{-l}}=\exp\!\Big(2\pi i\,\sum_{m=n-l+1}^{n} j_m 2^{\,n-m-l}\Big)=e^{2\pi i\,(0.j_{\,n-l+1}\ldots j_n)}, \]

Only terms with \(n-m-l<0\), i.e. \(m\ge n-l+1\), survive modulo \(1\); they assemble into the binary fraction \(0.j_{n-l+1}\ldots j_n=\sum_{p\ge1} j_{n-l+p}2^{-p}\). C

\[ H\lvert j_m\rangle=\frac{1}{\sqrt2}\Big(\lvert 0\rangle+e^{2\pi i\,(0.j_m)}\lvert 1\rangle\Big),\qquad e^{2\pi i\,0.j_m}=e^{i\pi j_m}=(-1)^{j_m}. \]

A single Hadamard produces exactly the leading bit of the required phase, \(0.j_m=j_m/2\). This seeds each output factor. B

\[ R_k=\begin{pmatrix}1&0\\[2pt]0&e^{2\pi i/2^{k}}\end{pmatrix},\qquad \text{controlled-}R_k\ \text{from qubit }m'\ \text{adds}\ e^{2\pi i\,j_{m'}/2^{k}}\ \text{to the target's }\lvert1\rangle. \]

Define the controlled-phase gate; it multiplies the target's \(\lvert1\rangle\) amplitude by \(e^{2\pi i/2^{k}}\) only when the control bit is \(1\). Diagonal, hence commuting and exactly implementable from the universal set. C

\[ H\ \text{on qubit }m,\ \text{then controlled-}R_2,R_3,\dots,R_{\,n-m+1}\ \text{from qubits }m{+}1,\dots,n \ \Rightarrow\ \big(\lvert0\rangle+e^{2\pi i\,(0.j_m j_{m+1}\ldots j_n)}\lvert1\rangle\big). \]

Each controlled-\(R_k\) appends the next binary digit \(j_{m+k-1}/2^{k}\) to qubit \(m\)'s phase; after all controls the phase equals the full fraction \(0.j_m\ldots j_n\). Diagonal gates commute so the order among controls is irrelevant. B

\[ \#H=\sum_{m=1}^{n}1=n,\qquad \#\,\text{controlled-}R=\sum_{m=1}^{n}(n-m)=\frac{n(n-1)}{2}. \]

Qubit \(m\) uses one Hadamard and \((n-m)\) controlled phases; sum the arithmetic series. A

\[ \text{Sequential build reverses bit order}\ \Rightarrow\ \lfloor n/2\rfloor\ \text{swaps}\ (\le 3\lfloor n/2\rfloor\ \text{CNOTs}). \]

The factor produced first (from qubit \(1\)) carries phase \(0.j_1\ldots j_n\), which the output convention assigns to the last wire; a bit-reversal swap network fixes the ordering. Each swap decomposes into \(3\) CNOTs from the assumed universal set. C

\[ N_{\text{gates}}=n+\frac{n(n-1)}{2}+O(n)=\frac{n(n+1)}{2}+O(n)=O(n^{2}). \]

Add Hadamards, controlled phases, and swaps; the quadratic controlled-phase term dominates. A

Result

\[ \mathrm{QFT}_{N}\,\lvert j\rangle=\frac{1}{2^{n/2}}\bigotimes_{m=1}^{n}\Big(\lvert0\rangle+e^{2\pi i\,(0.j_m j_{m+1}\ldots j_n)}\lvert1\rangle\Big),\qquad N_{\text{gates}}=\underbrace{n}_{H}+\underbrace{\tfrac{n(n-1)}{2}}_{\text{ctrl-}R}+O(n)=O(n^{2}). \]

Reading. The exponentially large Fourier matrix collapses to a product of single-qubit rotations whose phases are the trailing binary fractions of the input. Building each factor needs one Hadamard plus a decreasing ladder of controlled-phase gates, so the entire \(2^{n}\times2^{n}\) unitary is compiled in a number of primitive gates that grows only quadratically in the qubit count.

Units check. Every quantity is dimensionless: \(\mathrm{QFT}_N\) is a unitary operator (\(\mathrm{QFT}^{\dagger}\mathrm{QFT}=\mathbb{1}\), so it preserves the dimensionless norm \(\langle\psi|\psi\rangle=1\)); phases \(2\pi\cdot(\text{binary fraction})\) are pure angles in radians; and \(N_{\text{gates}}\) is a non-negative integer count. The prefactor \(2^{-n/2}\) enforces \(\big\lVert \mathrm{QFT}\lvert j\rangle\big\rVert=1\), since each of the \(n\) factors has norm \(\sqrt2\) and \((\sqrt2)^{n}/2^{n/2}=1\).

Limiting cases

\(n=1\): the sum is \(\tfrac{1}{\sqrt2}\sum_{k}e^{\pi i jk}\lvert k\rangle\); \(N_{\text{gates}}=1\) Hadamard and no controlled phases — the QFT is exactly \(H\).
\(n=2\): \(2\) Hadamards, \(1\) controlled-\(R_2\) (a controlled-\(S\)), and one swap.
Large \(n\): controlled-\(R_k\) with \(k\gtrsim \log_2(n/\varepsilon)\) contribute phase \(<\varepsilon\); dropping them (approximate QFT) cuts the count to \(O(n\log(n/\varepsilon))\) with total error \(<\varepsilon\).
All input bits zero (\(j=0\)): every phase is \(1\), output is the uniform superposition \(N^{-1/2}\sum_k\lvert k\rangle\), i.e. \(H^{\otimes n}\lvert0\rangle\).

Breaks when

The dimension is not a power of two. For a modulus \(N\ne2^{n}\), \(k/N\) has no finite binary expansion and step 2's clean bit weights \(2^{-l}\) do not close; the tensor-product factorisation of step 5 collapses and the \(O(n^{2})\) two-qubit circuit no longer represents \(\mathrm{QFT}_N\) exactly. One must embed in a larger power-of-two register or use dedicated modular-QFT constructions.
Controlled-phase angles cannot be realised to the needed precision. Exact \(e^{2\pi i/2^{k}}\) for large \(k\) is exponentially close to the identity; on hardware with finite gate fidelity or discrete (e.g. Clifford+T) gate sets these are only approximated, so the compiled unitary deviates from \(\mathrm{QFT}\) and phase estimation loses resolution.
Decoherence over the circuit depth. The controlled-phase ladder gives circuit depth \(O(n)\); if the qubit coherence time is short compared with the accumulated gate time the output is a mixed state and the interference that defines the transform is washed out.

Failure modes

Forgetting the swaps. Reading the sequential output without the bit-reversal network gives \(\mathrm{QFT}\) composed with a bit-flip permutation — correct up to relabelling wires, wrong if the register feeds a downstream circuit that assumes standard ordering.
Wrong controlled-phase angle. Using \(R_k=\mathrm{diag}(1,e^{2\pi i/k})\) instead of \(e^{2\pi i/2^{k}}\); the correct denominator is the power \(2^{k}\), not \(k\).
Double counting normalisation. Writing \(2^{-n}\) instead of \(2^{-n/2}\) out front; the amplitude, not the probability, carries the \(1/\sqrt N\).
Claiming a classical speedup. Asserting the QFT computes a Fourier transform of classical data faster; the \(N\) output amplitudes are not directly measurable, so no read-out advantage exists — the speedup is only inside a larger quantum algorithm.
Confusing QFT with the Hadamard transform. \(H^{\otimes n}\) has only real \(\pm1\) phases; the QFT's non-trivial controlled phases are exactly what distinguishes it, and dropping them silently reduces it to the Walsh–Hadamard transform.

Discussion

The physical content of the construction is that the Fourier phase \(e^{2\pi i jk/N}\) is a separable function of the output bits once \(k\) is written in binary. Separability of the exponent (step 3) is exactly what lets a global unitary be built from local gates: no genuinely \(n\)-body interaction is ever required, only pairwise controlled phases. The information about the input that any given output qubit needs is just a suffix of the input's binary string, encoded as a rotation angle — a very direct statement that the DFT is diagonal in the "frequency" degrees of freedom.

The thread to waves is immediate: the QFT changes basis from position eigenstates \(\lvert j\rangle\) to discrete momentum (wavenumber) eigenstates, the finite-dimensional analogue of the continuous transform \(\psi(x)\to\tilde\psi(k)\). The controlled-phase ladder is the circuit-level expression of the plane-wave kernel \(e^{ikx}\); halving the phase angle down the register mirrors the geometric spacing of Fourier modes. The thread to symmetry is that \(\mathrm{QFT}_N\) is the character table of the cyclic group \(\mathbb{Z}_N\): it diagonalises the cyclic shift operator, so eigenstates of translation (momentum states) are precisely its outputs — the reason it appears wherever a hidden periodicity (an unknown period \(r\) in Shor's algorithm) must be exposed.

More deeply, the \(O(n^{2})\) gate count sits against a lower-bound backdrop: any exact circuit for \(\mathrm{QFT}_N\) over a fixed finite gate set requires \(\Omega(n\log n)\) gates for constant precision, and the approximate QFT achieves \(O(n\log n)\) — so the naive quadratic circuit is within a logarithmic factor of optimal. The reason the transform is "easy" for a quantum computer but its output is not classically extractable is that \(\mathrm{QFT}\) is a change of basis, not a computation of a function value: measurement in the computational basis after the transform samples \(\lvert\tilde\psi(k)\rvert^{2}\), which is where phase estimation extracts eigenphases as sampled Fourier peaks. The exponential gap between \(O(n^{2})\) gates and the \(2^{n}\times2^{n}\) matrix size is the same gap that makes matrix-product-state and tensor-network methods powerful classically — the QFT is a low-depth, low-bond-dimension object in disguise.

Common misconceptions. The QFT does not let you Fourier-transform a list of numbers faster than the FFT for classical output; it transforms quantum amplitudes and only pays off when embedded in an algorithm (phase estimation) whose answer is a short bit string. It is also not the Hadamard transform: the two coincide only at \(n=1\).

Worked examples

Count every gate in the exact \(n=3\) QFT circuit.

Use \(\#H=n\), \(\#\text{ctrl-}R=\tfrac{n(n-1)}{2}\), \(\#\text{swap}=\lfloor n/2\rfloor\). A

\[ \#H=3,\qquad \#\text{ctrl-}R=\frac{3\cdot2}{2}=3,\qquad \#\text{swap}=\lfloor 3/2\rfloor=1. \]

Qubit 1: \(H,R_2,R_3\); qubit 2: \(H,R_2\); qubit 3: \(H\). A

\[ N_{\text{two-qubit}}=3\ (\text{ctrl-}R)+3\times1\ (\text{swap}=3\ \text{CNOT})=3+3=6,\qquad N_{\text{single}}=3. \]

One swap decomposes into three CNOTs. B

\[ n=3:\quad 3\ H,\ \ 3\ \text{controlled-}R\ (R_2,R_3,R_2),\ \ 1\ \text{swap},\quad \text{total }9\ \text{gates (or }6\text{ two-qubit CNOTs)}. \]

Reading. A three-qubit Fourier transform — an \(8\times8\) unitary — needs only nine primitive gates. Units check. All counts are dimensionless non-negative integers; \(\tfrac{n(n+1)}{2}=6\) matches \(3H+3R\) before swaps.

Compute \(\mathrm{QFT}_4\lvert 1\rangle\) explicitly (\(n=2,\ N=4\)) and confirm normalisation.

Apply the definition with \(j=1\). A

\[ \mathrm{QFT}_4\lvert1\rangle=\frac12\sum_{k=0}^{3} e^{2\pi i\,(1)(k)/4}\lvert k\rangle=\frac12\sum_{k=0}^{3} i^{\,k}\lvert k\rangle. \]

\(e^{2\pi i/4}=e^{i\pi/2}=i\). A

\[ =\frac12\Big(\lvert0\rangle+i\lvert1\rangle-\lvert2\rangle-i\lvert3\rangle\Big). \]

Insert \(i^0,i^1,i^2,i^3=1,i,-1,-i\). A

\[ \text{Product form: }j=1=(j_1 j_2)=(0\,1),\quad \tfrac12\big(\lvert0\rangle+e^{2\pi i\,0.j_2}\lvert1\rangle\big)\big(\lvert0\rangle+e^{2\pi i\,0.j_1 j_2}\lvert1\rangle\big). \]

Here \(0.j_2=0.1=\tfrac12\Rightarrow e^{i\pi}=-1\); \(0.j_1 j_2=0.01=\tfrac14\Rightarrow e^{i\pi/2}=i\). B

\[ \tfrac12(\lvert0\rangle-\lvert1\rangle)(\lvert0\rangle+i\lvert1\rangle)=\tfrac12(\lvert00\rangle+i\lvert01\rangle-\lvert10\rangle-i\lvert11\rangle). \]

After the bit-reversal swap this matches step 3 term by term. B

\[ \mathrm{QFT}_4\lvert1\rangle=\tfrac12\big(\lvert0\rangle+i\lvert1\rangle-\lvert2\rangle-i\lvert3\rangle\big),\qquad \textstyle\sum_k|c_k|^2=4\cdot\tfrac14=1. \]

Reading. Input \(\lvert1\rangle\) maps to a single-frequency comb whose amplitudes wind once around the unit circle in steps of \(i\). Units check. Each amplitude has magnitude \(\tfrac12\); four equal magnitudes square-sum to \(1\), confirming the state is normalised (dimensionless).

Problems

Show directly from the definition that the single-qubit QFT (\(n=1\)) equals the Hadamard gate.
Solution
For \(n=1,\ N=2\): \(\mathrm{QFT}\lvert j\rangle=\tfrac{1}{\sqrt2}\sum_{k=0}^{1}e^{2\pi i jk/2}\lvert k\rangle=\tfrac{1}{\sqrt2}\sum_k e^{i\pi jk}\lvert k\rangle\). For \(j=0\): \(\tfrac{1}{\sqrt2}(\lvert0\rangle+\lvert1\rangle)\). For \(j=1\): \(\tfrac{1}{\sqrt2}(\lvert0\rangle+e^{i\pi}\lvert1\rangle)=\tfrac{1}{\sqrt2}(\lvert0\rangle-\lvert1\rangle)\). The matrix is \(\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}=H\).
Give the exact gate tally for \(n=4\): number of Hadamards, controlled-phase gates, and swaps, and the leading-order total.
Solution
\(\#H=n=4\). \(\#\text{ctrl-}R=\tfrac{n(n-1)}{2}=\tfrac{4\cdot3}{2}=6\) (qubit 1: \(R_2,R_3,R_4\); qubit 2: \(R_2,R_3\); qubit 3: \(R_2\); qubit 4: none). \(\#\text{swap}=\lfloor4/2\rfloor=2\). Total before swaps \(=\tfrac{n(n+1)}{2}=10\); including \(2\) swaps (\(6\) CNOTs) the circuit is \(4\) single-qubit and \(6+6=12\) two-qubit gates. Leading order \(O(n^2)\).
Write the matrix of the controlled-phase gate used at "distance" \(k\) and evaluate its phase for \(k=1,2,3\). Explain why gates with large \(k\) may be dropped in the approximate QFT.
Solution
\(R_k=\begin{pmatrix}1&0\\0&e^{2\pi i/2^{k}}\end{pmatrix}\). \(k=1:\ e^{2\pi i/2}=e^{i\pi}=-1\) (this is \(Z\), realised by \(H\) itself as the leading digit). \(k=2:\ e^{2\pi i/4}=i\) (the \(S\) gate). \(k=3:\ e^{2\pi i/8}=e^{i\pi/4}\) (the \(T\) gate). The controlled version adds phase \(2\pi/2^{k}\), which for large \(k\) satisfies \(|e^{2\pi i/2^{k}}-1|\approx 2\pi/2^{k}\to0\); truncating all gates with \(2^{k}>n/\varepsilon\) introduces total operator-norm error \(<\varepsilon\) while reducing the count from \(O(n^2)\) to \(O(n\log(n/\varepsilon))\).
Derive the product form of \(\mathrm{QFT}_4\lvert j\rangle\) for general \(j=(j_1 j_2)\) and read off the two output factors' phases.
Solution
\(\mathrm{QFT}_4\lvert j_1 j_2\rangle=\tfrac12\big(\lvert0\rangle+e^{2\pi i\,0.j_2}\lvert1\rangle\big)\otimes\big(\lvert0\rangle+e^{2\pi i\,0.j_1 j_2}\lvert1\rangle\big)\). First factor phase \(0.j_2=j_2/2\Rightarrow e^{i\pi j_2}=(-1)^{j_2}\), produced by \(H\) on qubit 2. Second factor phase \(0.j_1 j_2=j_1/2+j_2/4\), produced by \(H\) on qubit 1 followed by controlled-\(R_2\) from qubit 2. Check \(j=1\ (j_1j_2=01)\): first factor \(-1\), second \(i\), giving \(\tfrac12(\lvert0\rangle-\lvert1\rangle)(\lvert0\rangle+i\lvert1\rangle)\), matching the worked example after the swap.
Compare the primitive-operation counts of the QFT and the classical FFT for \(n=20\) qubits (\(N=2^{20}\approx10^{6}\)), and state what quantity the exponential gap does and does not buy you.
Solution
QFT: \(\tfrac{n(n+1)}{2}=\tfrac{20\cdot21}{2}=210\) gates (order \(n^2\)); the approximate QFT would use \(\sim n\log_2 n\approx 20\cdot4.3\approx86\). Classical FFT: \(O(N\log_2 N)=2^{20}\cdot20\approx2.1\times10^{7}\) arithmetic operations. Ratio \(\sim10^{5}\) in operation count. What it buys: the change of basis on all \(2^{20}\) amplitudes at exponentially lower gate cost, enabling phase estimation. What it does not buy: classical read-out of the \(2^{20}\) transformed amplitudes — a single measurement returns one \(20\)-bit sample from \(|\tilde\psi(k)|^2\), so there is no speedup for Fourier-transforming stored classical data.