The quantum analog of the FFT - exponential speedup for frequency analysis
The Quantum Fourier Transform turns a state into its frequencies, stored as phases. It is the engine inside Shor's algorithm.
Pick a number of qubits and an input k. Each clock shows one amplitude's phase: the sizes all match, and the phases turn faster as k grows.
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.
Choose the number of qubits and an input state, then step through the circuit: a Hadamard and controlled phase rotations on each qubit, then SWAPs to finish.
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.
Hover over the chart to compare operation counts at any size N. At about a million points the DFT needs ~10¹², the FFT ~20 million, the QFT ~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.
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.
Set the number of counting bits and a true phase φ. Try φ = 0.25 or 0.375 with 3 bits for a single sharp peak, then an in-between φ and add bits to tighten the peak.
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.
Exact phases: When φ = k/2n exactly, QPE gives the correct answer with 100% probability. Try φ = 0.25 or 0.375 with 3 bits.
Approximate phases: When φ doesn't align with the grid, you get a distribution peaked near the true phase. More bits → tighter peak → better estimate.
Spot a mistake or have an idea?