Quantum Fourier transform

The quantum Fourier transform (QFT) is, without exaggeration, the single most important subroutine in quantum computing. It’s a quantum generalization of the discrete Fourier transform (DFT) that every signal-processing engineer already knows — and it runs exponentially faster on a quantum computer than the classical version on a classical computer.

Almost every quantum algorithm with an exponential speedup over the best known classical algorithm uses the QFT somewhere: Shor’s factoring, the hidden subgroup problem, phase estimation, HHL for linear systems. When you hear about “the period finding trick” in quantum computing, the engine behind it is the QFT.

What the Fourier transform does

The classical discrete Fourier transform takes a vector of $N$ numbers and produces another vector of $N$ numbers. Concretely, for an input $(x_0, x_1, \ldots, x_{N-1})$, the output is:

$y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \cdot e^{2\pi i jk/N}$

This is a change of basis: from the “position” basis (where each entry is a sample at a specific time or index) to the “frequency” basis (where each entry is a coefficient on a specific frequency component).

Finding periodic patterns in $x$ becomes trivial after the DFT, because periodic patterns in position correspond to concentrated energy at specific frequencies in the transformed vector.

The quantum version

The quantum Fourier transform is the unitary operator that does the same thing to a quantum state:

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

where $N = 2^n$ for an $n$-qubit register. For a general quantum state $\sum_j x_j |j\rangle$, the QFT produces $\sum_k y_k |k\rangle$ with the same coefficients as the classical DFT.

Why it’s exponentially faster

The classical fast Fourier transform (FFT) runs in $O(N \log N)$ time. That’s blazingly fast in practice — it’s how MP3 encoding works — but it’s still polynomial in $N$.

The quantum Fourier transform runs in $O(\log^2 N)$ quantum gates. That’s polynomial in $\log N$, i.e., polynomial in the number of qubits $n = \log N$. Expressed in terms of $N$, that’s exponentially faster than any classical FFT — because you’re not computing all $N$ output amplitudes explicitly; you’re preparing a quantum state whose amplitudes are the Fourier coefficients.

Here’s the catch (there’s always a catch): you can’t just read all the QFT output amplitudes. A measurement gives you one basis state, sampled from the probability distribution $|y_k|^2$. You get one sample, not the full transform.

But for some problems — especially period-finding — one sample is enough. That’s exactly the structure Shor’s algorithm exploits.

The circuit

The QFT circuit on $n$ qubits looks like this:

1. Apply $H$ to qubit 0.
2. Apply controlled-phase gates (each a rotation by $2\pi/2^k$) between qubit 0 and each subsequent qubit.
3. Apply $H$ to qubit 1.
4. Apply controlled-phase gates between qubit 1 and subsequent qubits.
5. … and so on for each remaining qubit.
6. Finally, reverse the qubit order with a series of SWAPs.

Total: $n$ Hadamards and $O(n^2)$ controlled-phase gates. That’s $O(n^2) = O(\log^2 N)$ total.

(Compare to the classical FFT, which performs $O(N \log N)$ classical operations — exponentially more.)

Inverse QFT

The inverse quantum Fourier transform $\text{QFT}^{-1}$ is almost the same circuit, just with reversed order and negated phase rotations. Both versions show up: QFT is used when you want to read out frequency information, QFT$^{-1}$ is used when you want to prepare a state from a frequency description.

QFT in algorithms

Roughly speaking:

• Deutsch-Jozsa and Bernstein-Vazirani use the QFT over $(\mathbb{Z}/2)^n$, which is just $H^{\otimes n}$ (a Hadamard on every qubit). It’s the simplest non-trivial Fourier transform.
• Simon’s algorithm also uses $H^{\otimes n}$, applied to extract periodicities in $(\mathbb{Z}/2)^n$.
• Shor’s algorithm uses the full QFT over $\mathbb{Z}/M$ for large $M$, to extract periodicities in modular arithmetic.
• Phase estimation uses the QFT$^{-1}$ to read out the eigenphase of a unitary.

All of these are instances of the same template: “do some quantum operation that encodes structure as a phase pattern, then apply the QFT (or its inverse) to convert that phase pattern into a measurable position pattern.”

What’s next

Shor’s algorithm. You have all the pieces.