Quantum Fourier transform

The quantum Fourier transform is the discrete Fourier transform acting on the amplitudes of a quantum state. For a power-of-two dimension, Shor's 1997 paper gives the efficient gate array, the same factorization as the classical fast Fourier transform, attributed there to Coppersmith and to Deutsch. On n qubits the transform uses on the order of n^2 gates, which is cheap next to modular exponentiation of an n-bit integer.

In Shor's algorithm the transform is applied to the exponent register after the periodic function has been computed. Measurement then returns a value close to a multiple of 1/r, where r is the order. Continued fractions finish the recovery classically. Quantum phase estimation is the later packaging of this idea as "read the phase of an eigenvalue." The 1997 paper's own subroutine is the Fourier transform written out for the order-finding state. The phase-estimation page separates Kitaev's measurement from the inverse-Fourier circuit of Cleve, Ekert, Macchiavello, and Mosca.