View source for 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 problem|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.

[[Category:Quantum Computing]]
[[Category:Mathematics]]