112
Part Three · B · Algorithms

Quantum Fourier transform

The fast Fourier transform of Chapter 6 takes about Nlog⁡NN\log N steps for NN numbers. The quantum Fourier transform acts on 2n2^n amplitudes with only about n2n^2 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 nn qubits, with N=2nN = 2^n, the QFT is the discrete Fourier transform of the amplitudes:

∣j⟩  →  1N∑k=0N−1e2πijk/N∣k⟩|j\rangle \;\to\; \frac{1}{\sqrt N}\sum_{k=0}^{N-1}e^{2\pi ijk/N}|k\rangle

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, ⨂l(∣0⟩+e2πi 0.jn−l+1…jn∣1⟩)/2\bigotimes_l(|0\rangle + e^{2\pi i\,0.j_{n-l+1}\ldots j_n}|1\rangle)/\sqrt2, where 0.ja…0.j_a\ldots 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 π/2,π/4,π/8,…\pi/2, \pi/4, \pi/8, \dots from each later qubit; finally reverse the qubit order. That is n(n+1)/2n(n+1)/2 gates. Don Coppersmith noticed in 1994 that the tiny rotations, by π/2k\pi/2^k for large kk, can be dropped: keeping only about log⁡n\log n of them per qubit changes the result negligibly, giving the approximate QFT with about nlog⁡nn\log n 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 x≡x0(modr)x \equiv x_0 \pmod r. Choose the period r=r = 4 and offset x0=x_0 = 1, with four qubits (N=16N = 16). After the QFT, the probability concentrates on multiples of N/rN/r: one measurement returns some kN/rkN/r, from which rr can be inferred. The offset changes only phases, not where the peaks are, which is why an unknown offset doesn’t matter. When rr doesn’t divide NN, the peaks blur but stay near kN/rkN/r; 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 n2n^2 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.

Why can the QFT use so few gates?tap
Its output on basis states factorizes into single-qubit states with binary-fraction phases.
Where do the peaks of a period-r state fall?tap
At multiples of N/r.
Why isn’t it a faster FFT?tap
The output amplitudes cannot be read out without many repetitions.

And one to work out. How many Hadamard and controlled-phase gates does the exact QFT on 10 qubits use, ignoring the final swaps?

gates =

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.

Next · Chapter 113
Phase estimation

Most famous fast quantum algorithms are phase estimation in disguise.

Turn the page