The Quantum Fourier Transform

The Quantum Fourier Transform on $n$ qubits is the unitary operator that acts on computational basis states $|0\rangle, |1\rangle, \dots, |N-1\rangle$, where $N = 2^n$, exactly as the classical discrete Fourier transform (DFT) acts on a vector of complex amplitudes. Precisely, the QFT is defined by its action on basis states:

Applied to a general state $\sum_j x_j |j\rangle$, the QFT produces $\sum_k y_k |k\rangle$ where $y_k = \frac{1}{\sqrt{N}}\sum_j \omega_N^{jk} x_j$ — precisely the classical DFT of the amplitude vector $(x_j)$. Because the DFT matrix is unitary (its rows are orthonormal, scaled by $1/\sqrt N$), the QFT is a legitimate quantum gate: a unitary operator on the $n$-qubit Hilbert space. The crucial structural fact, inherited directly from the classical Fast Fourier Transform (FFT), is that the DFT matrix factors into $O(\log N)$ sparse stages. The FFT exploits this factorization to compute a length-$N$ transform in $O(N \log N)$ arithmetic operations instead of the $O(N^2)$ naive matrix-vector product. The QFT exploits the same factorization, but because quantum superposition lets $N = 2^n$ amplitudes be manipulated by touching only $n$ qubits, the resulting circuit needs only $O(n^2) = O(\log^2 N)$ gates — exponentially fewer than even the FFT's already-efficient $O(N \log N)$, when cost is measured against the vector length $N$. The output amplitudes are never directly the answer: quantum amplitudes cannot be read out individually. Instead, the QFT is used to reshape a state's structure so that a subsequent measurement samples an integer that reveals information — most often, the period of a hidden function or the phase of an eigenvalue. This is the pattern used in Quantum Phase Estimation and, through it, in Shor's algorithm's Order-Finding Subroutine.

From binary fractions to a product formula

Write $j$ in binary as $j = j_1 j_2 \cdots j_n$ (most significant bit first), so $j = \sum_{l=1}^n j_l 2^{n-l}$. A standard algebraic manipulation — expanding the exponent $jk/N$ in binary and discarding integer multiples of $2\pi i$ (since $e^{2\pi i \cdot \text{integer}} = 1$) — shows that the QFT output state factors into a tensor product of single-qubit states:

where $0.j_l j_{l+1} \cdots j_n$ denotes the binary fraction $j_l/2 + j_{l+1}/4 + \cdots + j_n/2^{n-l+1}$. This product formula is the entire reason an efficient circuit exists: instead of building an entangled $N$-dimensional output vector directly, we build it as $n$ separate single-qubit factors, each computable by applying a Hadamard gate followed by a chain of controlled phase rotations conditioned on the other qubits' bit values.

The circuit, qubit by qubit

Concretely, for qubit $l$ (holding bit $j_l$), the required single-qubit factor is produced by: 1. A Hadamard gate on qubit $l$, which contributes the leading term $\frac{1}{\sqrt2}(|0\rangle + e^{2\pi i \cdot 0.j_l}|1\rangle)$. 2. A sequence of controlled phase gates $R_k$, each controlled by a later qubit $j_{l+k}$ and applying the phase $e^{2\pi i \, j_{l+k}/2^{k+1}}$ to qubit $l$'s $|1\rangle$ amplitude, refining the binary fraction one bit at a time. The standard controlled-phase gate used is

applying phase $e^{2\pi i /2^k}$ to the target qubit only when the control qubit is $|1\rangle$. After processing all $n$ qubits this way, a final bit-reversal permutation (via SWAP gates, or simply by relabeling wires) restores the natural ordering, because the recursive construction naturally outputs qubits in reversed order. ``` Algorithm: Quantum Fourier Transform on n qubits Input: quantum register |j_1 j_2 ... j_n> (n qubits, computational basis state) Output: state QFT_N|j_1...j_n> (N = 2^n), same register, bit-reversed order QFT(qubits[1..n]): for l = 1 to n: apply H to qubits[l] for k = 1 to n - l:

# controlled phase: control = qubits[l+k], target = qubits[l] angle = 2*pi / 2^(k+1) apply Controlled-Phase(angle) with control qubits[l+k], target qubits[l]

# qubits are now in reverse order relative to standard QFT convention for i = 1 to floor(n/2): SWAP qubits[i], qubits[n - i + 1] return qubits ``` Each qubit $l$ receives exactly one Hadamard and $(n-l)$ controlled-phase gates, for a total of

two-qubit and single-qubit gates, plus $\lfloor n/2 \rfloor$ SWAP gates for the final reversal (each a constant number of two-qubit gates), which does not change the asymptotic count.

Reading the diagram

Each row is a qubit-wire, time flows left to right. Qubit $q_1$ receives a Hadamard, then three controlled-phase gates $R_2, R_3, R_4$ controlled successively by $q_2, q_3, q_4$, each contributing a finer binary digit to its phase. Qubit $q_2$ receives one fewer controlled rotation, and so on down to $q_4$, which receives only a Hadamard. The dashed line marks the final swap stage that undoes the bit-reversal inherent in the recursive construction.

Gate complexity. As counted above, the circuit uses exactly $n$ Hadamard gates and $\binom{n}{2}$ controlled-phase gates, plus $O(n)$ SWAPs, for a total of

elementary gates, where $n = \log_2 N$. This is exponentially smaller than the classical FFT's $O(N \log N) = O(N \cdot n)$ arithmetic operations when both are measured in terms of the vector dimension $N$: the QFT is polynomial in $\log N$, while the FFT is polynomial in $N$ itself.

Why the circuit is correct. The correctness argument is an algebraic unrolling of the product formula, not an appeal to a black box. Starting from $|j\rangle = |j_1 j_2 \cdots j_n\rangle$, apply $H$ to qubit 1:

since $e^{2\pi i \cdot 0.j_1} = e^{\pi i j_1} = (-1)^{j_1}$, matching $H|0\rangle$ and $H|1\rangle$ exactly. The controlled-$R_2$ gate, controlled by $j_2$, then multiplies the $|1\rangle$-amplitude of qubit 1 by $e^{2\pi i \, j_2/4}$ exactly when $j_2 = 1$, upgrading the phase to $e^{2\pi i \, 0.j_1 j_2}$. Each successive controlled-$R_k$ gate appends one more binary digit of the fraction. After all $n-1$ controlled rotations on qubit 1, its state is exactly

which is precisely the $l=1$ factor of the product formula. The same argument applies verbatim to qubit $l$, using only bits $j_l, \dots, j_n$ (since qubit $l$ never depends on bits before it — those have already been "used up"). Multiplying the $n$ single-qubit factors together, by linearity of tensor product over the sum defining each factor, reconstructs exactly

which is the definition of $\text{QFT}_N|j\rangle$. Since the circuit's action agrees with the definition on every basis state $|j\rangle$, and both the circuit and the QFT are linear operators, they agree on all superpositions — establishing full correctness. Because the circuit is manifestly a product of unitary one- and two-qubit gates, it is automatically unitary, confirming the QFT is a valid quantum operation without needing a separate unitarity check.

Why $O(n^2)$ is unavoidable (in the exact circuit) — and how to beat it approximately. The construction directly mirrors the recursive butterfly structure of the Cooley–Tukey FFT: splitting a length-$N$ DFT into two length-$N/2$ DFTs on even- and odd-indexed inputs, recombined with "twiddle factor" phase corrections. Classically, this recursion has $\log N$ levels and each level touches all $N$ points, giving $O(N\log N)$. Quantum-mechanically, each level touches only $O(n)$ qubits with a chain of controlled rotations, and there are $n$ levels, giving $O(n^2)$. The controlled-phase angles $2\pi/2^{k+1}$ shrink exponentially as $k$ grows. In the Approximate QFT (AQFT), rotations by angle smaller than some threshold $\epsilon/n$ are simply omitted. A careful error analysis (each dropped rotation perturbs the final state's fidelity by at most $O(\epsilon/n)$, and errors add subadditively across $O(n\log(n/\epsilon))$ retained gates) shows the total output state's fidelity loss is $O(\epsilon)$ while gate count drops to $O(n \log(n/\epsilon))$ — essentially $O(n\log n)$ for constant precision. This tradeoff is used in practice: fewer gates means less decoherence exposure on real noisy hardware, at the cost of a controllably small approximation error.

Honest limitation. The QFT's speed advantage is entirely in transforming amplitudes you already have in superposition. It does not let you read out the Fourier coefficients of an arbitrary unknown state efficiently — a single measurement after the QFT yields only one sampled output, governed by the Born rule, not the full spectrum. Its power is unlocked only when combined with problem structure (periodicity, eigenphase encoding) that concentrates the post-QFT measurement distribution on informative outcomes — exactly the setup engineered by Quantum Phase Estimation.

Take $n = 3$ qubits, so $N = 8$, and trace $\text{QFT}_8 |5\rangle$ where $5 = 101_2$, i.e. $j_1 j_2 j_3 = 1,0,1$. By the product formula, we need $0.j_1 j_2 j_3 = 0.101_2 = 1/2 + 0/4 + 1/8 = 5/8$, and its shifted versions:

So the product formula predicts

Trace through the circuit to confirm this matches, tracking qubit 1 (the most work, since it accumulates the most rotations): 1. Start: $|j_1 j_2 j_3\rangle = |1,0,1\rangle$. 2. Apply $H$ to qubit 1 ($j_1 = 1$): produces $\frac{1}{\sqrt2}(|0\rangle - |1\rangle)$, i.e. phase $e^{\pi i} = -1$ on $|1\rangle$. Current fraction: $0.j_1 = 0.1 = 1/2$. ✓ matches $e^{2\pi i /2} = -1$. 3. Apply controlled-$R_2$ on qubit 1, controlled by qubit 2 ($j_2 = 0$): control is $0$, gate does nothing. Fraction stays $0.10 = 1/2$. 4. Apply controlled-$R_3$ on qubit 1, controlled by qubit 3 ($j_3 = 1$): control is $1$, multiplies $|1\rangle$-amplitude by $e^{2\pi i/8} = e^{\pi i /4}$. New phase: $e^{\pi i} \cdot e^{\pi i/4} = e^{5\pi i /4}$. Fraction: $0.101 = 5/8$. ✓ matches the table exactly. Repeating for qubit 2 ($j_2=0$: Hadamard gives phase $+1$; controlled-$R_2$ from $j_3=1$ multiplies by $e^{2\pi i/4} = i$, giving total phase $i$ ✓) and qubit 3 ($j_3 = 1$: Hadamard alone gives phase $-1$ ✓) confirms every factor. The numerical output (unnormalized ordering before bit-reversal correction) is exactly

and this is a genuinely entangled-looking but actually product state — a hallmark of QFT outputs on basis-state inputs. Expanding fully gives all 8 amplitudes with $|{\pm i^k}|/\sqrt8$ magnitudes, matching the classical DFT of the indicator vector $e_5 \in \mathbb{C}^8$, i.e. $y_k = \frac{1}{\sqrt8}\omega_8^{5k}$ — exactly the definitional formula, confirming the circuit computed the right transform.

:::warning[The single most dangerous mistake is treating QFT output amplitudes as directly readable data. A measurement collapses the state to one sampled integer governed by the squared amplitudes — the QFT's value comes entirely from how algorithms like phase estimation engineer that sampling distribution to concentrate on the answer, not from any ability to "read off" a spectrum in one shot.]:::

The QFT was not invented as a standalone object; it emerged as the mathematical engine inside quantum algorithms designed to exploit periodicity, drawing directly on a century of classical Fourier and Fast Fourier Transform theory.

The QFT is the shared engine inside every quantum algorithm that exploits the <span class="wiki-link-missing">Hidden Subgroup Problem</span> structure. Shor's factoring algorithm uses the QFT to extract the period of modular exponentiation, which — via elementary number theory — reveals a nontrivial factor of the integer being factored; this is the same machinery underlying attacks on RSA-style public-key cryptography, motivating the entire field of post-quantum cryptography. The discrete logarithm algorithm, which breaks Diffie–Hellman and elliptic-curve cryptosystems, uses the identical QFT-based period-finding idea generalized to two registers. Beyond cryptanalysis, the QFT is the computational core of Quantum Phase Estimation, which itself underlies quantum simulation algorithms for estimating molecular ground-state energies in quantum chemistry, and appears inside the HHL algorithm for linear systems and various quantum machine learning proposals that rely on eigenvalue extraction. The Order-Finding Subroutine used inside Shor's algorithm is, concretely, phase estimation applied to a modular-multiplication unitary, with the QFT performing the final frequency extraction step. Any serious quantum computing hardware or compiler stack — from superconducting-qubit platforms to trapped-ion systems — includes an optimized QFT or approximate-QFT circuit generator as a standard library primitive, precisely because so many higher-level algorithms compile down to it.

Ask the tutor: How does the inverse QFT inside Quantum Phase Estimation turn an unknown eigenphase into a sharply peaked measurement distribution?