Quantum Fourier Transform (QFT) Explained

What is the Quantum Fourier Transform?

The Discrete Fourier Transform (DFT) maps a sequence of N complex numbers to another sequence of N complex numbers representing the frequency content of the original. The classical Fast Fourier Transform (FFT) computes this in O(N log N) time. The Quantum Fourier Transform does the same mathematical operation, but acts on the amplitudes of a quantum state rather than on an explicit list of values.

Given an n-qubit quantum state with 2^n amplitudes, the QFT applies the DFT to those amplitudes using O(n^2) quantum gates -- exponentially fewer operations than the O(n * 2^n) classical cost of the FFT on 2^n numbers. This is the source of the potential speedup.

The foundational role of the QFT in quantum computing comes from the fact that many problems reduce to finding periodicity or phase information hidden in a quantum state. The QFT transforms that hidden structure into a form that measurements can extract efficiently.

How the QFT circuit works

The QFT circuit on n qubits is built from two types of gates: Hadamard gates and controlled phase rotation gates. Working from the most significant qubit down, the pattern is:

Apply a Hadamard gate to the first qubit, then apply controlled phase rotations from each subsequent qubit. The phase rotation applied from qubit k to qubit j is R_k, where R_k is a diagonal gate that adds phase 2pi / 2^k. Repeat this process for each qubit. After processing all n qubits, apply a bit reversal (swapping qubit order) to match the standard DFT output ordering.

The total gate count is n Hadamard gates plus n(n-1)/2 controlled phase rotations, giving O(n^2) gates. For n = 10 qubits (a 1024-element transform), the QFT needs roughly 55 two-qubit gates -- far fewer than the classical FFT's ~10,000 operations on the same number of elements.

The intuition: each Hadamard gate puts a qubit into a superposition that encodes a frequency component. The controlled phase gates then add the precise phase relationships between frequencies that define the Fourier transform. The result is a quantum state whose amplitudes are exactly the DFT coefficients of the input amplitudes.

Where QFT is used

The QFT appears as a subroutine in several of the most significant quantum algorithms:

Shor's algorithm uses the QFT to find the period of the modular exponentiation function. Once the period is found, classical number theory extracts the prime factors. The QFT is what makes Shor's algorithm exponentially faster than the best known classical factoring algorithms.

Quantum Phase Estimation (QPE) uses the QFT to extract the eigenvalue (phase) of a unitary operator. QPE is itself a subroutine in the HHL algorithm for linear systems, quantum simulation of chemistry (used in VQE as a reference), and other algorithms. The QFT is what converts the phase, encoded in a quantum register, into a measurable binary value.

Quantum signal processing and more recent algorithmic frameworks like Quantum Singular Value Transformation (QSVT) also leverage QFT-based phase techniques as building blocks.

QFT vs classical FFT

A common misconception is that the QFT can replace the classical FFT for general signal processing tasks. It cannot, for a fundamental reason: quantum measurement.

After applying the QFT, the 2^n output amplitudes exist in superposition. To read out all of them, you would need to measure many copies of the output state -- which requires preparing the input state exponentially many times. The net cost is no better than classical, and potentially worse.

The QFT is useful precisely when its output is consumed by a subsequent quantum operation rather than read out directly. In Shor's algorithm, the QFT output feeds into a measurement that extracts just the period information -- a single number -- from the full frequency spectrum. That selective extraction is where the speedup lives.

The lesson is general: quantum speedups require careful end-to-end design. A fast quantum subroutine only produces an overall speedup if the input preparation and output extraction are also efficient.