Quantum Fourier transform
The fast Fourier transform of Chapter 6 takes about steps for numbers. The quantum Fourier transform acts on amplitudes with only about gates: exponentially fewer operations. It sounds like an exponentially faster FFT. It isn’t, because the transformed numbers stay locked inside the amplitudes, and one measurement gives you only one sample. What the QFT does superbly is find periods, and that is enough to break RSA.
On the plate: a periodic state before the QFT, and the sharp peaks after it.
The transform
On a register of qubits, with , the QFT is the discrete Fourier transform of the amplitudes:
It is unitary, so it is a valid quantum operation. The key identity: the output for a basis input factorizes into a product of single-qubit states, , where is a binary fraction. That product form is what makes a short circuit possible. Established
The circuit
For each qubit in turn: a Hadamard, then controlled phase rotations by from each later qubit; finally reverse the qubit order. That is gates. Don Coppersmith noticed in 1994 that the tiny rotations, by for large , can be dropped: keeping only about of them per qubit changes the result negligibly, giving the approximate QFT with about gates. Robert Griffiths and Chi-Sheng Niu showed in 1996 that when the QFT is followed by measurement, the controlled rotations can be replaced by measurements and classically controlled single-qubit gates, which needs only one qubit at a time.
Periods become peaks
Prepare a state with amplitude only on . Choose the period 4 and offset 1, with four qubits (). After the QFT, the probability concentrates on multiples of : one measurement returns some , from which can be inferred. The offset changes only phases, not where the peaks are, which is why an unknown offset doesn’t matter. When doesn’t divide , the peaks blur but stay near ; Chapter 114 handles that with continued fractions.
Not a faster FFT
To use an FFT you need all the output numbers. The QFT’s outputs are amplitudes; reading them requires repeating the computation many times and sampling, which costs at least as much as the classical FFT. The QFT pays off only when the question is about a global feature of the transformed state, a period or a phase, that a few samples reveal. Loading arbitrary classical data into amplitudes is itself expensive (Chapter 120). Established
What you now have
The QFT and its product formula, the circuit, the approximate and semiclassical versions, how periodic states turn into peaks, and why the QFT is not a replacement for the FFT.
· · ·
Three questions to carry with you.
And one to work out. How many Hadamard and controlled-phase gates does the exact QFT on 10 qubits use, ignoring the final swaps?
Sources: D. Coppersmith, IBM Research Report RC 19642 (1994), arXiv:quant-ph/0201067. R. B. Griffiths and C.-S. Niu, Phys. Rev. Lett. 76, 3228 (1996). M. A. Nielsen and I. L. Chuang, ch. 5. Checked by code: the 16-point QFT matrix is unitary; a period-4 state maps to peaks at 0, 4, 8, 12; the gate circuit in the plate matches the DFT matrix.