QFT vs FFT Complexity

The Quantum Fourier Transform (QFT) on $n$ qubits computes the same mathematical object as the classical Discrete Fourier Transform (DFT) on $N = 2^n$ elements — yet it does so with exponentially fewer operations. Understanding exactly where the saving comes from is essential before using the QFT as a subroutine in phase estimation or Shor's algorithm.

The classical FFT

The Fast Fourier Transform (FFT) invented by Cooley and Tukey evaluates the DFT of $N$ numbers in $O(N \log N)$ operations. For $N = 2^n$ this is $O(2^n \cdot n)$ arithmetic operations. No classical algorithm can do better in general — computing all $N$ output amplitudes requires touching at least $N$ values.

Gate count of the QFT

The QFT circuit on $n$ qubits uses exactly $n$ Hadamard gates (one per qubit) and

$\frac{n(n-1)}{2}$

two-qubit controlled-phase gates, for a combined total of

$n + \frac{n(n-1)}{2} = \frac{n(n+1)}{2} = O(n^2)$

elementary gates. Since $n = \log_2 N$ , this is $O((\log N)^2)$ — exponentially fewer operations than the classical $O(N \log N)$ .

To see where the controlled-phase count comes from: qubit $k$ (counting from the most significant, $k = 0, 1, \ldots, n-1$ ) receives controlled- $R_j$ rotations from each of the $n - 1 - k$ subsequent qubits, giving

$(n-1) + (n-2) + \cdots + 1 + 0 = \frac{n(n-1)}{2}$

controlled-phase gates in total. Adding the $n$ Hadamards recovers the $\frac{n(n+1)}{2}$ overall gate count.

The exponential caveat

The $O(n^2)$ gate count is a genuine asymptotic improvement, but it carries a crucial qualification: the QFT only prepares the Fourier-transformed quantum state. Measuring that state samples from the output distribution, but does not directly hand you all $N$ Fourier coefficients.

In algorithms like phase estimation, only a single phase is needed — and the QFT delivers it efficiently. In Shor's algorithm, the QFT reveals the period of a modular function, again requiring only the dominant frequency. These are tasks where the quantum speedup is real and useful.

If your goal were to store and inspect all $N$ Fourier coefficients, the QFT would not help: you would need $O(N)$ measurements to reconstruct the full output, recovering the classical $O(N \log N)$ barrier.

Side-by-side comparison

| Quantity | Classical FFT | QFT | |---|---|---| | Input size | $N = 2^n$ complex numbers | $n$ -qubit state ( $2^n$ amplitudes) | | Operation count | $O(N \log N) = O(n \cdot 2^n)$ | $O(n^2)$ gates | | Output | All $N$ Fourier coefficients | Quantum state encoding them | | Readable outputs | $N$ (all coefficients) | $O(1)$ (one sample per measurement) |

The table makes the trade-off concrete. The quantum circuit is exponentially faster at building the Fourier state, but exponential effort is needed to read it out in full. The power of the QFT lies in downstream quantum operations that exploit the state directly, without collapsing it first.

Approximate QFT

In practice, controlled- $R_j$ gates with $j \gt \lceil \log_2(1/\epsilon) \rceil$ contribute a global error less than $\epsilon$ and are dropped. This reduces the gate count to $O(n \log(n/\epsilon))$ while preserving the output to within any desired precision — a further practical advantage over exact classical methods.