algorithmsCircuit workspace
13 min read
The Quantum Fourier Transform
The quantum analog of the discrete Fourier transform, built from H and controlled-phase gates, and the circuit that computes it exactly.
Suggested before this lesson
Grover's algorithm was the last lesson built from tools you already had, , , . The next two algorithms, Quantum Phase Estimation and Shor's algorithm, are both built around a new primitive: the Quantum Fourier Transform (QFT). This lesson is the transform itself; the next two put it to work.
The classical discrete Fourier transform turns a list of numbers into a list of frequency components. The QFT is the same idea, applied to a quantum state's amplitudes instead of a classical list, done entirely with unitary gates. It maps a computational basis state to an equal-weighted superposition over every basis state, with each one's phase encoding :
Compare this to on a single qubit (): , . is the 1-qubit QFT; the general QFT is what you get generalizing that same "spread into a phase-encoded superposition" idea to qubits, .
Slide and watch the output phases rotate around the circle: every basis state keeps the same magnitude, only the phase spacing between them changes with .
Output phases
k = 1 / 7
Output amplitude on basis state n
gives every one of the 8 basis states equal weight , but a different phase each. The dots are those 8 phases for the you picked, evenly spaced around the circle, steps apart each time. The highlighted dot is (always phase 0); the arrow marks , whose phase alone, , is exactly what distinguishes one value of from another.
Building the -qubit case needs a gate this course hasn't used yet: controlled-phase, , qc.cp(theta, control, target). It applies a phase rotation to the target, but only on the branch where the control qubit is , otherwise it does nothing. is physically symmetric in its two qubits (swapping which one you call "control" gives the identical gate), which is why circuit diagrams draw it as a plain dot on both wires rather than 's dot-and-ring.
For 2 qubits ():
on qubit 1 starts spreading it into superposition; the controlled-phase gate lets qubit 0 imprint a phase onto that superposition depending on its own value; on qubit 0 spreads it too; the final puts the two qubits back in the order the definition above expects. Try it on (): the amplitudes come out as on respectively, exactly for .
Circuit
x
h
cp
swap
Step through the circuit: after gate 5 of 5
6 / 6
Exact State
| Basis state | Re | Im | Probability |
|---|---|---|---|
| 0.500 | 0 | ||
| 0 | 0.500 | ||
| -0.500 | 0 | ||
| 0 | -0.500 |
Live preview of the circuit detected in your code
The -qubit QFT repeats the same idea per qubit: , then a cascade of gates from every later qubit, each with a smaller angle (, then , then , ...), then move to the next qubit, finishing with a layer of s to reverse the qubit order. The circuit above is exactly this pattern's smallest nontrivial case, one , one , one more , one . Every extra qubit adds one more and one more cascade, growing the gate count as , exponentially fewer gates than the the fastest classical FFT needs for the same size input, though the two aren't directly comparable: the QFT acts on amplitudes you can't read out directly, and turning that into a genuine speedup for a real problem is exactly what Quantum Phase Estimation (next lesson) does.
Python
Python