ConceptAdvancedAlgorithmic techniques

Quantum Fourier Transform

The quantum Fourier transform is the discrete Fourier transform applied to the amplitudes of $n$ qubits, implemented with $O(n^2)$ gates; it is central to phase estimation and Shor's algorithm.

For $N=2^n$ we define $$\mathrm{QFT}|x\rangle=\frac{1}{\sqrt N}\sum_{y=0}^{N-1}e^{2\pi ixy/N}|y\rangle.$$ It is a unitary matrix. It has a useful product form: the output is a tensor product of qubits, each $\tfrac{1}{\sqrt2}(|0\rangle+e^{2\pi i\,0.x_j\dots x_{0}}|1\rangle)$ with binary fractions of the bits of $x$. The circuit is built from it: on each qubit $H$, then controlled phase gates $CP(\pi/2^k)$, then SWAP gates to reverse the order, $O(n^2)$ gates in total. Coppersmith (1994) described an approximation that drops very small rotations without a large loss of accuracy.

Compared with the fast Fourier transform (FFT), which needs $O(N\log N)=O(n2^n)$ operations, the QFT looks exponentially faster. But this does not mean we obtain the Fourier coefficients: they are stored in the amplitudes and can only be read by measurement, which gives a single sample. Its benefit appears when we need only a property that the samples reveal, such as a periodicity whose amplitudes concentrate on a few values, as in phase estimation and order finding in Shor's algorithm.

In the algorithms lab you can apply the QFT to an integer $x$ and watch the phases in the state vector.

Mathematical formula

$$\mathrm{QFT}|x\rangle=\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}e^{2\pi i\,xy/N}|y\rangle$$

Worked example

$n=1$: $\mathrm{QFT}|x\rangle=\tfrac{1}{\sqrt2}(|0\rangle+(-1)^x|1\rangle)$, i.e. the QFT on one qubit is $H$. $n=2$, $x=1$: the amplitudes are $\tfrac12(1,i,-1,-i)$ for $y=0,1,2,3$; each probability is $\tfrac14$, and all the information is in the phases. So measuring $\mathrm{QFT}|x\rangle$ directly gives a uniform distribution that does not reveal $x$.

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
  2. Don Coppersmith (1994). An approximate Fourier transform useful in quantum factoring. IBM Research Report RC19642 (arXiv:quant-ph/0201067, 2002) doi:10.48550/arXiv.quant-ph/0201067
  3. John Watrous / IBM Quantum (2025). Fundamentals of Quantum Algorithms (course). IBM Quantum Learning quantum.cloud.ibm.com