The quantum Fourier transform: catching the period

Build the quantum Fourier transform at the heart of Shor’s algorithm with two qubits. See how a periodic state turns into peaks that reveal the period.

What does a Fourier transform do?

The classical Fourier transform splits a signal into its frequencies: it is how you find the notes in a song or a repeating pattern in a measurement. The quantum Fourier transform (QFT) does the same to amplitudes: it turns a repeating (periodic) amplitude pattern into a few distinct results that reveal the period.

Shor’s algorithm turns factoring into a period-finding problem and uses the QFT to find the period.

A two-qubit QFT

The QFT consists only of H gates and controlled-phase gates. On two qubits it is four steps: H on q1, a CS (controlled quarter turn) with q0 as control and q1 as target, H on q0, and finally a SWAP that fixes the qubit order. On n qubits the gate count is about n²/2, exponentially less than the n·2ⁿ operations of the classical fast Fourier transform.

In the playground the first H prepares an equal mix of 00 and 10: in a four-box array boxes 0 and 2 are filled, so the period is 2. The QFT turns this into two peaks at 00 and 10; the distance between the peaks is 4 / period = 2.

Careful: the QFT is not a magic wand

The QFT computes the Fourier transform of the amplitudes, but we can’t read it out directly; we only get one measurement. That is why the QFT is useful for problems whose result concentrates in a few distinct peaks, such as period finding and phase estimation. In the next lesson we use the inverse QFT to read a phase.

Try it yourself

Remove the first H gate: the input is now just 00, so there is no period. The QFT makes all four results 25%; no peak remains.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

The QFT turns a periodic amplitude pattern into peaks that reveal the period.
It consists of H and controlled-phase gates; n qubits need about n²/2 gates.
Shor’s algorithm uses the QFT to find a period.
The result is read only by measurement; the QFT is useful where the peaks are distinct.

Test yourself

If boxes 0 and 2 of a four-box state are filled, where are the peaks after the QFT?

00 and 01
00 and 10
All four results are equal

Show the answer

00 and 10. The period is 2, so the peaks appear 4 / 2 = 2 apart, at results 0 and 2, that is 00 and 10.

← Grover in depth: oracle and diffusion · Phase estimation: measure a gate’s secret →