Quantum Fourier transform (QFT)

The quantum Fourier transform is the unitary operator implementing the discrete Fourier transform on a quantum register:The opposite exponent defines its inverse. Orthogonality of the finite Fourier phases makes the output vectors orthonormal and the map unitary.

The transform turns periodicity in input amplitudes into structure in measurement probabilities. A uniform state supported on a periodic arithmetic sequence gives peaks at frequencies related to that period, making the transform useful in quantum order finding. For $N=2^n$, a dyadic quantum Fourier transform circuit uses Hadamard gates and controlled phase gates. The circuit transforms amplitudes without printing their numerical values; obtaining a useful answer still requires an appropriate state preparation and measurement.

The Quantum Fourier Transform (QFT) is a quantum analogue of the classical discrete Fourier transform (DFT). It is a linear transformation that takes quantum states and transforms them into a superposition of frequencies, which is incredibly useful in various quantum algorithms, especially in algorithms for factoring integers and solving problems in quantum computing.