Quantum Fourier transform

The quantum Fourier transform (QFT) is the quantum-mechanical analogue of the discrete Fourier transform, and it is the mathematical engine behind the exponential speedup of Shor's algorithm and several other quantum algorithms. Where the classical discrete Fourier transform on N points requires O(N log N) operations, the quantum Fourier transform acts on a superposition of states and requires only O((log N)²) quantum gates — an exponential reduction that is the signature of genuine quantum advantage.

The QFT does not directly output the Fourier spectrum of a function. Instead, it transforms a quantum state whose amplitudes encode the function values into a state whose amplitudes encode the Fourier coefficients. This means the QFT cannot be used to extract the full spectrum classically — doing so would require measuring the state, collapsing the superposition, and obtaining only a single sample. But for period-finding, symmetry-detection, and hidden subgroup identification, a single sample is often sufficient. The QFT is thus not a general-purpose accelerator but a precision tool for specific structural extraction.

The transform is implemented as a sequence of Hadamard gates and controlled phase rotations, and its efficiency depends critically on the quantum circuit model. Whether alternative models of quantum computation — adiabatic quantum computation, for instance — can implement an equally efficient Fourier-like transform remains unresolved.