Quantum Fourier transform

The quantum Fourier transform (QFT) is the quantum-circuit implementation of the discrete Fourier transform, acting directly on the amplitudes of a quantum state rather than on a classical array of numbers. On $n$ qubits ($N=2^n$-dimensional), it is the unitary map

$|x⟩\mapsto \frac{1}{\sqrt{N}}{\sum }_{y=0}^{N-1}{e}^{2\pi ixy/N}|y⟩$

implementable with $O(n^2)$ elementary gates, compared with the $O(n{2}^n)$ operations a classical fast Fourier transform would need to reach a comparable $2^n$-dimensional output — an exponential resource gap, though the QFT is not by itself an algorithm that produces a directly readable answer, since the transformed amplitudes still have to be extracted by measurement.

The QFT is the core subroutine behind quantum phase estimation, which in turn underlies Shor’s algorithm for integer factoring and most other exponential quantum speedups known for period-finding problems. Its standard circuit uses controlled-phase gates between every pair of qubits, which requires all-to-all qubit connectivity; adapting it to hardware with only nearest-neighbor connectivity (a linear or 2D grid, as most physical qubit platforms provide) without giving up its gate-count efficiency is a separate, practically important compilation problem from the QFT’s abstract definition.

Related papers

• Coppersmith, “An approximate Fourier transform useful in quantum factoring”, IBM Research Report RC 19642 (1994) — the original construction of the efficient quantum circuit.
• Shor, “Algorithms for quantum computation: discrete logarithms and factoring”, Proc. 35th FOCS (1994) — introduces the factoring algorithm that made the QFT’s phase-estimation role central to the field.