The Famous Algorithms

The quantum Fourier transform

Reading a hidden period out of a superposition

~12 minLesson 17 of 24Written by Claude Fable 5

Every algorithm in this module has been a way of arranging amplitudes so that interference answers a question. Grover concentrated weight onto one marked item. The quantum Fourier transform concentrates weight onto a hidden rhythm: hand it a state whose amplitudes repeat every $r$ steps, and it collapses that repetition into a few sharp spikes that reveal $r$ . That single trick is the engine that breaks RSA in the next lesson.

What it does not do

"The transform hands you the period r directly." Not quite. It reshapes the amplitudes so that a measurement is very likely to land on a multiple of

N / r

. From one such multiple you infer

r

with a little classical arithmetic. The transform does the hard part - exposing the rhythm - but you still read out one number, once, and reason back to the period.

Watch repetition become location

The input below is a comb: an amplitude spike every $r$ bins across $N = 16$ positions. Change the period $r$ and watch where the transform piles the output. Then slide the offset - the whole comb shifts, but the output peaks stay locked in place.

Periodscope: a comb with hidden period r goes in; the transform sends all the weight onto the multiples of N/r.

Period r

Offset0

Input: a spike every r = 4 bins (4 teeth), starting at 0.

Output probabilities |X[k]|^2: sharp peaks on the multiples of N/r = 4 (that is 0, 4, 8, 12).

Slide the offset and the peaks do not move - only the position of the comb changed, not its period. That is the point: the transform reads the spacing, not the starting place. Measure the output and you land on a multiple of 4, which hands you N/r - and from that, r.

Two facts fall out of playing with it. The output peaks sit on the multiples of $N / r$ , so their spacing is the reciprocal of the input's: a tightly repeating input (small $r$ ) spreads its output peaks far apart, and vice versa. And the offset is invisible in the peak positions - it only turns their phases. The transform reads spacing, not starting point.

The transform, stated

The is a change of basis. On $N$ basis states it sends each $∣ j ⟩$ to an even spread over all outputs, each output $∣ k ⟩$ carrying a phase that winds at a rate set by $j$ :

QFT ∣ j ⟩ = \frac{1}{N} k = 0 \sum N - 1 e^{2 π i j k / N} ∣ k ⟩ .

You do not need to grind through this sum - the full derivation and the circuit that implements it live on the reference sheet. What matters is what it does to a periodic superposition. Feed in a state that is an equal spread over the positions ${s, s + r, s + 2 r, \dots}$ - the comb - and the winding phases from all those equally spaced terms reinforce each other only when $k$ is a multiple of $N / r$ , and cancel everywhere else. The result concentrates on exactly those multiples:

comb with period r QFT peaks at k \in {0, \frac{N}{r}, \frac{2 N}{r}, \dots} .

Why the offset drops out

Shifting the comb by a start position

s

multiplies every output amplitude by a phase

e^{2 π ik s / N}

. A phase has magnitude one, so it cannot move a peak or change how likely you are to measure it - it only rotates it. That is precisely why the next lesson can find a period without knowing where the periodic pattern begins: the answer it needs survives an unknown offset untouched.

So the QFT is the frequency-reading half of the interference toolkit. Where Grover rotated toward a marked answer, the QFT tunes into a hidden frequency. And because a measurement afterward returns a multiple of $N / r$ , one run plus some arithmetic recovers the period $r$ that a periodic function was hiding.

Lock it in

The QFT is a change of basis: it sends |j> to an even spread of outputs whose phases wind at a rate set by j.
On a comb of period r it interferes constructively only at multiples of N/r and destructively elsewhere, so the output is a few sharp peaks.
The peak spacing N/r is the reciprocal of the input period; a measurement returns one such multiple, from which you recover r.
Shifting the input only adds phases, so the peak positions are blind to the offset - the reason period-finding works without knowing the start.

Check yourself

You put a superposition with period r through the QFT. Where does the output concentrate?

Why is the QFT the key subroutine in Shor's algorithm?

Recall: what structure does the QFT expose, and where does its output land?

The one input-output behavior Shor depends on. Try to state it, then check.

The QFT exposes periodicity. Given a superposition whose amplitudes repeat with period

r

over

N

positions, it concentrates the output onto the multiples of $N / r$ , with everything else cancelling by interference. A measurement then returns one such multiple, and the offset of the input pattern only affects phases, so it does not disturb the peak positions - which is exactly what lets Shor recover a period without knowing where the pattern starts.

Match each idea to its role in the transform.

drop here

produces sharp peaks at multiples of N/r

drop here

reveals the hidden period as a frequency

drop here

returns one multiple of N/r

drop here

the quantity Shor's algorithm needs

Primary source

Nielsen and Chuang, Quantum Computation and Quantum Information (chapter 5)

Chapter 5 derives the QFT, its efficient circuit, and the phase-estimation and period-finding routines built on it - the full sum this lesson only stated, worked out step by step.^[1]

Next: Shor's algorithm, which turns factoring into period-finding and lets this transform bring down RSA.^[2]

Sources