Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 39 ยท Quantum Algorithms

The Quantum Fourier Transform

Understand the quantum Fourier transform, build its circuit from Hadamard and controlled-phase gates, and use it to detect periods.

The quantum Fourier transform (QFT) is the engine inside Shor's algorithm and quantum phase estimation. It is the discrete Fourier transform applied to the amplitudes of a quantum state. On n qubits it needs only about n^2 / 2 gates, while the fastest classical FFT on 2^n numbers needs about n * 2^n operations.

Be careful with what that means. The QFT does not let you read out all the Fourier coefficients: they are amplitudes, and a measurement gives you just one sample. Its power appears when a state has a hidden periodic structure, because interference then concentrates the amplitude on a few outcomes that reveal the period.

Definition

Let N = 2^n and w = exp(2*pi*i / N). The QFT maps a basis state |j> to

Text
QFT|j> = (1/sqrt(N)) * sum over k of  w^(j*k) |k>

It is a unitary matrix with entries w^(jk) / sqrt(N). Compared with NumPy, np.fft.ifft(x) * sqrt(N) uses exactly this sign convention.

Python The QFT matrix against NumPy's FFT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every output amplitude has the same magnitude 1/sqrt(8). Only the phases differ, which is why a QFT of a basis state looks "flat" if you measure it.

The product form and the circuit

The QFT has a remarkable factorized form. Write j in binary as j1 j2 ... jn (j1 the most significant bit). Then

Text
QFT|j1...jn> = (|0> + e^(2*pi*i*0.jn)|1>) x (|0> + e^(2*pi*i*0.j(n-1)jn)|1>) x ... x (|0> + e^(2*pi*i*0.j1...jn)|1>)  / sqrt(N)

where 0.j1j2... is a binary fraction. Each output qubit is in a single-qubit state with a phase determined by some input bits. That leads to a circuit with two kinds of gates:

  • a Hadamard on a qubit, which writes the phase (-1)^(its bit), and
  • controlled phase gates R_k = diag(1, exp(2*pi*i / 2^k)), which add the smaller fractional phases from the less significant bits.

Finish with swaps to reverse the qubit order. The circuit for qubit 0 down to qubit n-1 is:

flowchart LR
    A["H on q0"] --> B["R2 from q1"] --> C["R3 from q2"] --> D["H on q1"] --> E["R2 from q2"] --> F["H on q2"] --> G["Swap q0 and q2"]

The three-qubit QFT: Hadamards, controlled phases of shrinking angle, then a reversal.

Build it and compare it with the matrix:

Python QFT from H, controlled-phase and SWAP gates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two agree to machine precision. In practice, circuits often drop the very small rotations (an approximate QFT), because angles below about 1/n barely change the result.

Finding a period

Suppose a register of N = 16 amplitudes is nonzero only at positions 0, r, 2r, ... for some period r (this is the kind of state the first half of Shor's algorithm prepares). After the QFT, the amplitude concentrates at multiples of N/r. Measuring one such multiple, with a little classical post-processing, reveals r.

Python QFT turns a period into peaks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The shift offset changes only phases, so the peak positions are identical whatever the starting offset. That shift-invariance is exactly what makes the QFT good at finding periods.

Gotchas

  • Qubit order. The raw circuit produces the output in reversed order, which is why the swaps are needed. Many libraries offer a version without them, if you prefer to undo the order yourself.
  • Inverse QFT. Phase estimation uses the inverse QFT: apply the gates in reverse order with negated angles.
  • Cost of preparing input. A fast transform is useless if loading the data costs 2^n operations. The QFT works best on states produced by earlier quantum steps.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Roughly how many gates does the QFT on n qubits need?

    There are n Hadamards and about n^2/2 controlled-phase gates (plus n/2 swaps), so it grows quadratically in n.
  2. 2. Which gates make up the QFT circuit?

    Hadamards create the leading phase, controlled phases add the finer fractions, and swaps restore the bit order.
  3. 3. Why can't you use the QFT to read out all Fourier coefficients of a classical vector?

    Amplitudes cannot be read directly. The QFT helps when interference concentrates probability on informative outcomes.
  4. 4. What does the QFT do to a state whose amplitudes repeat with period r?

    Periodic structure interferes constructively only at multiples of N/r.

Summary

  • The QFT is the unitary with entries w^(jk)/sqrt(N), using about n^2/2 gates.
  • Its circuit is Hadamards, controlled phase gates R_k of shrinking angle, and a final swap layer.
  • Output amplitudes of a basis state all have the same magnitude; the information is in the phases.
  • It turns hidden periodicity into measurable peaks, which is the core of phase estimation and Shor's algorithm.

Next: Quantum Phase Estimation