Quantum Fourier Transform

The quantum version of the discrete Fourier transform.

The Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is one of the most important subroutines in quantum computing. It is the quantum analogue of the Discrete Fourier Transform (DFT), but it runs exponentially faster and operates on quantum amplitudes rather than classical data.

What the QFT does:

The QFT maps computational basis states to Fourier basis states:

QF T ∣ j ⟩ = \frac{1}{N} k = 0 \sum N - 1 e^{2 π ij k / N} ∣ k ⟩

For an n-qubit state, $N = 2^{n}$ . The QFT encodes the frequency content of the input amplitude distribution into the output amplitudes.

Classical vs quantum:

	Classical FFT	QFT
Input	N real/complex numbers	Quantum state of log₂N qubits
Output	N Fourier coefficients	Quantum state encoding Fourier coefficients
Runtime	O(N log N)	O(n²) = O((log N)²)
Reads output	All N values	Only via measurement (partial)

The exponential speedup is real, but limited: you cannot read all N output amplitudes, measurement collapses to one sample. The QFT is useful when you only need a specific property of the transform, which is why it works so well in QPE and Shor's.

Circuit structure:

The QFT circuit has a repeating pattern. On this platform qubit 0 is the least significant bit, so the circuit works from the most significant qubit down. For each qubit j from n-1 down to 0:

1.Apply Hadamard to qubit j
2.Apply controlled-phase rotations: for each qubit k < j, apply $C P (2 π / 2^{j - k + 1})$ with qubit k as control and qubit j as target

After processing all qubits, reverse their order with SWAP gates to correct for bit-reversal.

QFT vs classical DFT: what's exponentially faster

The QFT circuit uses only $O (n^{2})$ gates to transform n qubits, equivalent to an $O ((lo g N)^{2})$ algorithm for $N = 2^{n}$ values. The classical FFT needs O(N log N) operations. However, reading the full output requires N measurements, eliminating the speedup for full readout. QFT gives an advantage only when used as a subroutine: as in QPE, where you only need a few measurement outcomes.

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.

Part of: Quantum Algorithms

Learn the algorithms that make quantum computers powerful.

Previous lessonQuantum Walks Next lessonQuantum Phase Estimation

This lesson is part of Pro

Unlock Quantum Algorithms and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground