Source-verifiedLevel 3

Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the quantum analog of the discrete Fourier transform, transforming computational basis states into phase-encoded frequency states using only O(n^2) gates for n qubits.

What it means

The QFT maps the computational basis state |j⟩ to a superposition with phases encoding the frequency components: QFT|j⟩ = (1/sqrt(2^n)) * sum_k e^(2*pi*i*j*k/2^n) |k⟩.It requires only O(n^2) gates (H and controlled-phase gates), compared to O(n*2^n) for the classical FFT -- an exponential improvement.The QFT is a key subroutine in Shor's algorithm (period finding), quantum phase estimation, and quantum simulation.The circuit consists of Hadamard gates and controlled-Rk rotation gates applied in a specific pattern, followed by qubit reversal.

Everyday analogy

The QFT is like converting a musical chord (time domain) into its individual notes (frequency domain) -- quantum mechanics does this conversion exponentially faster.
Think of it as a prism that splits white light into a rainbow of colors: the QFT reveals the hidden frequency structure of quantum states.

Common misconceptions

  • The QFT speedup does NOT directly translate to faster signal processing -- you cannot efficiently extract all Fourier coefficients from the output due to measurement collapse.
  • The QFT circuit is NOT the same as the classical FFT algorithm -- it achieves exponential speedup in gate count but reading out results requires different techniques.

Key takeaways

  • QFT transforms computational basis to frequency basis using O(n^2) gates.
  • Exponentially fewer gates than classical FFT's O(n*2^n).
  • Key subroutine in Shor's algorithm and quantum phase estimation.

Check your understanding

How many gates does the QFT require for n qubits?

  1. A.O(n)
  2. B.O(n^2)
  3. C.O(2^n)
  4. D.O(n*2^n)
Show the answer

Answer: B. O(n^2)

Why: The QFT circuit requires O(n^2) gates (Hadamards and controlled rotations), exponentially fewer than the classical FFT's O(n*2^n).

Builds on

QubitSuperpositionHadamard GatePhase (S) GateCNOT Gate

Primary source: Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172

Circuit form per Coppersmith (1994), arXiv:quant-ph/0201067.

Learn it hands-on

This concept is part of a 46-level curriculum with an interactive simulator and Lumen, a tutor whose answers are verified before you see them. Levels 1–5 are free.

Start freeSee the curriculum