Quantum Fourier Transform (QFT)

The QFT is the quantum analogue of the discrete Fourier transform — implemented in O(n²) gates instead of O(n2ⁿ), it is the engine inside Shor and phase estimation.

Gates

O(n²) — H + controlled-phase

Classical DFT

O(N log N)

Role

period/phase extraction

What it does

The QFT maps computational basis states to Fourier basis states using a ladder of Hadamards and controlled-phase rotations, followed by qubit-order reversal (swaps). It never gives you the amplitudes directly, but it concentrates periodic structure into measurable peaks.

Circuit sketch

Where it's used

Period-finding (Shor), phase estimation, and any algorithm that exploits periodicity or convolution structure.

In code (Qiskit)

from qiskit.circuit.library import QFT
qc = QFT(num_qubits=3)