What does "Fourier transform" even mean for a superposition of qubits?
Simon's algorithm (topic 10) found a hidden XOR-period using n Hadamard gates and ordinary linear algebra, because XOR-periods live in the group (ℤ/2ℤ)ⁿ and the Hadamard transform is exactly the Fourier transform over that group. Real periods (the ones behind factoring) live in ℤ/2tℤ instead, a bigger, different group, and finding them needs the Fourier transform for that group: the quantum Fourier transform. These three topics build it, use it to read out an unknown phase, and use that to recover a period: the exact chain Shor's algorithm runs, derived here instead of asserted there.
The discrete Fourier transform is a completely classical, century-old idea: given N numbers, produce N new numbers that describe the original data as a sum of oscillations of different frequencies. A signal with period p in the original domain produces spikes concentrated at multiples of N/p in the frequency domain: a fact used everywhere from audio compression to X-ray crystallography.
The quantum Fourier transform is the identical formula, applied to the amplitudes of a quantum superposition instead of an array of classical numbers. That sounds like a small change, but it has one large consequence: because a quantum computer's basic gates act on the amplitudes of an n-qubit state directly, the QFT on 2n amplitudes can be built from only O(n²) elementary gates: exponentially fewer than the O(n·2ⁿ) needed by even the classical Fast Fourier Transform on that many numbers. That specific quantity is genuinely exponentially cheaper to compute quantum-mechanically.
The honest catch, immediately: that gate-count saving does not mean you get to read out all 2n transformed amplitudes cheaply: a measurement still only ever returns one basis state, and topic 03's distinguishability limit applies exactly as before. The QFT is fast to run; the output is exactly as hard to fully read out as any other quantum state. Its actual usefulness (topics 12 and 13) comes from arranging things so the interesting answer is concentrated on a handful of outcomes, the way the period-4 example above concentrates on exactly 4 peaks out of 16, so that a small number of measurements is enough.
On n qubits (N=2n basis states), the QFT is the unitary:
QFT|x⟩ = (1/√N) Σ_y exp(2πi xy / N) |y⟩
the exact discrete Fourier transform formula, applied to a basis state. It's built from a cascade of Hadamard gates and controlled phase-rotation gates Rk = diag(1, exp(2πi/2k)) between every pair of qubits, followed by a qubit-order reversal. O(n²) gates total, all standard textbook circuit constructions (not reproduced here; the claim checked below is the transform's actual behaviour, not one specific gate layout for it).
Special case, consistency check: for n=1 (N=2), the formula reduces exactly to the Hadamard gate. QFT and Simon's algorithm's Hadamard transform (topic 10) are literally the same object at the smallest possible size, which is precisely why Simon's algorithm is the group-(ℤ/2ℤ)ⁿ special case of the general hidden-subgroup pattern the QFT solves for larger groups.
Periodicity ↦ sparsity, exactly. If |ψ⟩ = (1/√p) Σk=0p−1 |kN/p⟩ for p dividing N (a signal supported only on multiples of N/p), its QFT is supported only on multiples of N/p in the transformed basis, not approximately concentrated there, exactly zero everywhere else. Verified numerically: unitarity (F†F=I) holds to machine precision for n=1–5; the n=1 case matches the Hadamard matrix to 9×10⁻¹⁷; period-4/8/16 test signals on N=16/32/64 transform to spikes at exactly the predicted multiples of N/p, with zero probability everywhere else.
The engine inside topics 12 and 13 The QFT is never the end of a quantum algorithm on its own: it's the last step of a pipeline that has already arranged for the answer to be periodic or concentrated. The next two topics are that pipeline, built one stage at a time: phase estimation uses the QFT to read out an unknown number to fixed precision, and period finding uses phase estimation to recover the period behind Shor's algorithm.
Check yourself
A signal that repeats every 4 positions out of 16 goes through the quantum Fourier transform. What does the output look like?
Periodicity in one basis becomes sparsity in the other: a period-4 signal on 16 points transforms to exactly 4 peaks, at the multiples of 16/4, with zero probability elsewhere.