The Quantum Fourier Transform
The quantum Fourier transform (QFT) takes patterns in a quantum state's amplitudes, especially repeating ones, and turns them into chance peaks at matching frequencies. It uses only about n²/2 gates on n qubits. A normal FFT on the same data needs about n·2ⁿ steps. The catch: its input and output live in amplitudes you cannot read directly. So the QFT is an engine inside algorithms like phase estimation and Shor's. It is not a faster FFT you can just plug in.
What does a Fourier transform do, and what does the QFT transform?
Why care? The QFT is the engine behind the most famous quantum speedup, Shor's algorithm. Once you see what it does, and what it cannot do, a lot of quantum hype falls apart.
Start with the normal kind. A Fourier transform takes a signal and tells you which frequencies are in it, and how strong each one is. A frequency is how often something repeats. The music bars on a speaker app that jump for bass and treble are a live Fourier transform. So is tapping your foot to find a song's beat. Say a signal repeats every r steps, across M samples. Its Fourier transform shows spikes at multiples of M/r. The FFT (fast Fourier transform) is the fast method normal computers use for this.
The quantum Fourier transform does the same math to a different thing: the amplitudes of a quantum state. A refresher: an n-qubit state gives each of the 2ⁿ bitstrings an amplitude. An amplitude is a complex number. Its size, squared, is the chance of that result. Its angle is its phase. You cannot see a phase from a single measurement. (See probability amplitudes and amplitudes and phase.)
Treat the 2ⁿ amplitudes as 2ⁿ samples of a signal. The QFT gives back a new state. Its amplitude on string k is the sum of all the input amplitudes, each turned by some phase:
output(k) = (1/√8) × Σₓ input(x) · e^(2πi·x·k/8) (written for 3 qubits, 8 amplitudes).
Two notes on the symbols, since both show up everywhere from here on. Σₓ means: add up one term for each input value x. And e^(iθ) is short for a phase factor. Picture it as an arrow of length 1, pointing at angle θ (in radians). At θ = 0 it equals +1. At θ = π it equals −1. At θ = π/2 it equals i. So e^(2πi·x·k/8) just means the length-1 arrow at angle 2π·x·k/8. Nothing more.
Here is the key idea to hold on to: a repeating pattern in the amplitudes becomes a pile of chance at the pattern's frequency. And chance, unlike phase, is something a measurement can see. That one sentence is why the QFT sits inside phase estimation and Shor's algorithm.
Where the music example breaks: a speaker app shows you every bar at once. The QFT does not. You only get one sample per shot, as the rest of this chapter shows.
- What does the 3-qubit QFT circuit look like?
- Run it: QFT of |000⟩INTERACTIVE
- Change the input to |100⟩INTERACTIVE
- Why does measuring right after a QFT show nothing?
- How does the QFT reveal a period?
- Run it: the comb becomes two peaksINTERACTIVE
- What is the QFT actually for?
- What does the QFT look like on real hardware?
You’ve read the opening of chapter 7. Pro unlocks the other 8 sections — plus every chapter of every course, with circuits you can run right on the page. That’s $11.99 a month, about the price of a coffee, or $99.99 a year (save 30%). The first chapter of every course, and the whole math course, stay free.