The quantum analog of the FFT - exponential speedup for frequency analysis
The Quantum Fourier Transform is the quantum version of the discrete Fourier transform. While the classical FFT takes O(N log N) operations, the QFT achieves O(log² N) — an exponential speedup. It transforms the computational basis into a "frequency" basis where phases encode information.
The QFT is the engine behind some of the most important quantum algorithms: Shor's factoring algorithm, quantum phase estimation, and the hidden subgroup problem. Understanding QFT is key to understanding quantum computational advantage.
The QFT maps each computational basis state |k⟩ to a uniform superposition where every amplitude has the same magnitude 1/√N but different phases. The phases rotate faster for larger k — just like higher frequency modes in classical Fourier analysis. Each clock shows the phase of one amplitude component.
Key insight: In the Fourier basis, all probabilities are equal (1/N each). The information is encoded entirely in the phases between amplitudes. This is fundamentally different from the computational basis where information is in the probabilities.
The QFT circuit has an elegant recursive structure: for each qubit, apply a Hadamard gate followed by controlled phase rotations from all lower qubits. The controlled-Rk gate applies a phase of e2πi/2k. After all qubits are processed, reverse the qubit order with SWAPs. The total gate count is O(n²) where n = log₂N — exponentially better than classical.
The naive Discrete Fourier Transform takes O(N²) operations. The Fast Fourier Transform (Cooley-Tukey, 1965) brought this down to O(N log N) — one of the most important algorithms of the 20th century. The QFT goes further to O(log² N). For N = 1,048,576 points: DFT needs ~10¹² operations, FFT needs ~20 million, QFT needs just ~400.
Hover over the chart to see exact operation counts. The QFT line is barely visible because it grows so slowly — that's the exponential quantum advantage! But remember: QFT alone doesn't let you read the transform; its power comes from being embedded in larger algorithms.
Phase estimation is the killer application of QFT. Given a unitary U and its eigenstate |u⟩ with U|u⟩ = e2πiφ|u⟩, QPE finds φ to n bits of precision using n counting qubits. It works by: (1) creating superposition on counting qubits, (2) applying controlled-U2k gates, (3) inverse QFT. The measurement distribution peaks sharply at the integer closest to φ·2n.
When φ = k/2n exactly, QPE gives the correct answer with 100% probability. Try φ = 0.25 or 0.375 with 3 bits.
When φ doesn't align with the grid, you get a distribution peaked near the true phase. More bits → tighter peak → better estimate.