Quantum Computing · Part B — 06

The QFT, Built Up

The Quantum Fourier Transform is the beating heart of phase estimation and Shor’s algorithm. Underneath the name it does something simple: it turns a stored number into a winding rate — a pattern of phases spinning across the register — using nothing but Hadamards and controlled phase turns.

↩ before you start · keep these handy

·From QI 0.2: a phase e^iθ is a point on the unit circle; multiplying phases adds angles.

·From QC 02: a controlled-phase gate stamps a phase on the |11⟩ branch only.

·From QI 8d: Shor uses the QFT to read a hidden period — this is how it’s built.

🔑 symbol decoder · every new mark, in plain words

QFTthe gate that sends |j⟩ to an even spread of all states, each carrying a phase that winds at rate j. ω = e^2πi/Nthe basic “root of unity” — one Nth of a full turn around the circle. N = 2ⁿthe number of basis states for n qubits (here n = 3, so N = 8). Rᵤa controlled phase turn of 2π/2ᵤ — the small rotations that build the QFT. winding ratehow many full phase turns sweep across the register — this is the input number j. bit reversalthe QFT circuit outputs the qubits in reverse order, fixed by a few SWAPs at the end.

feel

A number becomes a spin

Hand the QFT a plain number j and it hands back a register where every slot has the same loudness but a different phase, and those phases march around the circle at a speed set by j. Small j: a lazy, slow wind. Big j: a fast spin. The information has moved from the bit pattern into the rhythm — which is exactly what the period-finding algorithms want to read.

🎹 everyday picture

A musical chord and its frequency spectrum hold the same information two ways: one as a wiggling waveform in time, the other as a few bars showing which pitches are present. A Fourier transform converts between them. The QFT is that conversion done on amplitudes — it trades a state labelled by position for one labelled by frequency. Periodic things look messy in position and crisp and peaked in frequency.

recapThe QFT trades position for frequency: a number j becomes a phase that winds across the register at rate j.

play

Watch the phases wind

Three qubits, so N = 8 output slots. Each clock below is one output amplitude — all the same size 1/√8, differing only in phase. Slide the input number j and watch the hands wind faster: slot k carries phase 2π·jk/8.

▸ QFT phase wheelQFT|j⟩ = (1/√8) ∑ₖ ωjk|k⟩

input number j = {{ j }}  ·  binary |{{ jbin }}⟩  ·  winding rate {{ j }} turn(s) across the register

{{ note }}

recapQFT|j⟩ gives equal magnitudes with phases winding at rate j — the number is now a frequency.

math

From the formula to the circuit

The definition is one line — the same Fourier sum you’d write classically, now acting on amplitudes:

QFT|j⟩ = (1/√N) ∑k=0N−1 e2πi jk/N |k⟩

The magic is that this sum factors across the qubits, and each factor is just a Hadamard followed by a few controlled phase turns. So the circuit, qubit by qubit, is:

Count them: about n²/2 gates for n qubits. The classical FFT needs n·2ⁿ — exponentially more. (The catch, in the misconceptions below, is that you can’t read all 2ⁿ outputs.)

✎ worked example · QFT of |1⟩ on N = 4

QFT|1⟩ = ½ ∑ₖ e2πi (1)k/4|k⟩,  k = 0,1,2,3
phases: k=0 → 0°, k=1 → 90° (= i), k=2 → 180° (= −1), k=3 → 270° (= −i)
= ½(|0⟩ + i|1⟩ − |2⟩ − i|3⟩)
all four magnitudes are ½; the input 1 shows up as one full wind of phase across the four slots. ✓

recapThe Fourier sum factors into H + controlled-Rᵤ gates per qubit; ~n²/2 gates, plus a bit-reversal swap.

⚠ common misconceptions

“The QFT is exponentially fast, so it instantly Fourier-transforms huge data.” It transforms the amplitudes, which you can’t read out one by one — measurement gives a single sample. The QFT is only useful when a clever circuit makes the answer show up as a peak you’re likely to measure.

“QFT and the classical DFT are different transforms.” Same transform, same matrix — only the way it’s applied differs. The QFT runs it on a superposition with a tiny circuit.

“You can skip the bit-reversal swaps.” The circuit naturally produces the output qubits in reversed order. Either swap them at the end, or just relabel — but don’t forget it’s there.

✓ you can now

✓write the QFT as the Fourier sum and read it as “number → winding rate”

✓draw the QFT circuit: H + controlled-Rᵤ per qubit, then bit-reversal swaps

✓compute a small QFT by hand and see the phases wind

✓explain why ~n²/2 gates isn’t a free lunch — you still must measure

← 05 Amplitude Amplification next · 07 Phase Estimation →