Part IV. Protocols and Algorithms

Quantum Fourier Transform

The quantum Fourier transform never appears in a headline and appears inside nearly every serious algorithm: it is the basis change that turns hidden periodicity into bits you can measure.

Listen to this chapter

The QFT is a lens, not an engine: it creates no structure of its own, but any algorithm that has written periodic or phase information into amplitudes needs exactly this transform to read that structure back out.

By the end you will be able to compute a small QFT by hand, say what the transform does to a basis state, and explain why it shows up precisely where algorithms hide answers in phase.

Core concepts: Fourier basis, roots of unity, phase progressions, orthogonality, inverse QFT.

Notice how little machinery the transform needs — one Hadamard per qubit plus controlled phases between them. The circuit is the easy part; what matters is what it decodes: periodic phase structure written by an earlier subroutine.

A change of basis, not a speedup button

The quantum Fourier transform maps computational-basis states to Fourier-basis states — superpositions whose amplitudes step through regular phase progressions. Applied to a state with no periodic structure, it gives you nothing you wanted. Applied to a state whose phases encode a period, the inverse QFT concentrates that information into measurement outcomes you can read.

That is why the QFT appears inside phase estimation and period finding rather than on its own poster. Those algorithms arrange for the answer to live in phases; the QFT is the reader. Understanding it as a basis change — the same conceptual move as the Hadamard, one chapter-sized step further — keeps both halves of that sentence in view.

The transform, precisely

On an $n$ -qubit register with $N = 2^{n}$ , the definition is:

QFT_{N} ∣ x ⟩ = \frac{1}{N} y \sum e^{2 π i x y / N} ∣ y ⟩

Each input basis state spreads over all output basis states with equal magnitude, distinguished only by phase. For two qubits, $N = 4$ , and the phases step through the fourth roots of unity:

1, i, - 1, - i

Different inputs produce different phase progressions, and those progressions are mutually orthogonal — which is why the transform is unitary, reversible, and implementable as a circuit of one Hadamard per qubit plus controlled phase gates. The circuit is a corollary of the definition, not the definition.

Worked example: two qubits, four progressions

Applying the definition at $N = 4$ gives the full table:

QFT ∣0 ⟩ QFT ∣1 ⟩ QFT ∣2 ⟩ QFT ∣3 ⟩ = \frac{1}{2} (∣0 ⟩ + ∣1 ⟩ + ∣2 ⟩ + ∣3 ⟩) = \frac{1}{2} (∣0 ⟩ + i ∣1 ⟩ - ∣2 ⟩ - i ∣3 ⟩) = \frac{1}{2} (∣0 ⟩ - ∣1 ⟩ + ∣2 ⟩ - ∣3 ⟩) = \frac{1}{2} (∣0 ⟩ - i ∣1 ⟩ - ∣2 ⟩ + i ∣3 ⟩)

These are not four arbitrary states. Read each row as a clock face: $∣1 ⟩$ steps the phase by a quarter turn per basis index, $∣2 ⟩$ by a half turn, $∣3 ⟩$ by three quarter turns. The input's identity is encoded in the stepping rate. Now run the logic in reverse, as the inverse QFT does: if some earlier subroutine has produced a superposition whose phases step at a rate set by a hidden period, the inverse transform piles the amplitude onto basis states that name that period. Phase in, bits out.

Where the intuition fails

The first trap is memorizing the circuit and losing the transform. Controlled phase gates and a final swap are implementation details; the meaning is the basis change. If you can draw the circuit but cannot say what $QFT ∣1 ⟩$ is, you have the plumbing without the water.

The second trap is crediting the QFT with speed it does not have. The transform helps exactly when the problem has Fourier-relevant structure — periodicity, phase patterns, modular arithmetic — and an earlier step has encoded that structure into amplitudes. Without the structure, applying the QFT is an expensive way to rearrange ignorance.

The engineering view

For a computer scientist, the QFT is the quantum cousin of the discrete Fourier transform from signal processing, with one decisive difference: you cannot read the coefficients. A classical DFT hands you the whole spectrum; the QFT holds it in amplitudes, and measurement returns samples. Algorithm design is the art of arranging for the coefficient you want to carry most of the probability before you measure.

The implementation checklist for any QFT-based workflow:

choose the register size — it sets both resolution and circuit depth;
prepare the phase-structured input state;
apply the QFT or its inverse;
measure;
interpret the sampled bit string classically.

Precision and sample distributions matter even for clean, noise-free algorithms. A QFT on paper is exact; a QFT in a workflow is a statistical component.

What this buys you in diligence

When a claim invokes the QFT, ask four questions: what periodic or phase structure exists in the problem, which subroutine prepares it, how many qubits of precision the transform needs, and what classical post-processing consumes the samples. A claim with crisp answers has a real algorithm inside it. A claim that treats "QFT" as a synonym for "fast" has a diagram where the argument should be.

Exercise

Build the table yourself. Derive the two-qubit QFT table from the definition, then audit it.

Compute all four output rows directly from $QFT_{N} ∣ x ⟩$ at $N = 4$ .
Verify normalization for each row, and verify orthogonality for one pair of rows by hand.
Compare against a classical four-point DFT table: what is the same, and what changes because quantum measurement samples rather than lists coefficients?
Explain, for one concrete algorithm, how phase structure becomes useful only because measurement and post-processing can extract it.
Close with one sentence: when does a QFT component strengthen an algorithm claim, and when is it decoration?

Check your understanding

Answer without notes: what does the QFT do to a computational-basis state, and why does that help only when the input carries periodic structure?

A passing answer describes the equal-magnitude phase progressions, names the roots of unity, and connects the inverse QFT to reading out a hidden period — without claiming the transform creates the period.

Oral defense: derive one row of the two-qubit table on a whiteboard and explain its phase stepping to a colleague.

If you get stuck

If the roots of unity or the normalization feel shaky, revisit Chapter 3 (Probability vs Amplitude) for amplitude arithmetic and Chapter 6 (Interference as the Engine of Quantum Algorithms) for why phase relationships — not magnitudes alone — drive measurement outcomes. Then rebuild the table; deriving it once beats reading it five times.