= Quantum Fourier transform
{title2=$\operatorname{QFT}_N$}
{wiki}
= QFT
{c}
{synonym}
The quantum Fourier transform is the <unitary operator> implementing the discrete <Fourier transform> on a quantum register:
$$
\operatorname{QFT}_N|k\rangle=\frac1{\sqrt N}\sum_{j=0}^{N-1}e^{2\pi ijk/N}|j\rangle.
$$
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.
Back to article page