EquationAdvancedEquations

Quantum Fourier Transform Definition

The discrete Fourier transform acting on the amplitudes of $n$ qubits.

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

Symbols

$x$Input number
$y$Output number
$N$Space dimension $2^n$
$e^{2\pi i xy/N}$Phase factor (root of unity)

$x,y\in\{0,\dots,N-1\}$ are integers represented by bit strings (in Qiskit's little-endian order), $N=2^n$, and $e^{2\pi ixy/N}$ are roots of unity. The matrix is unitary, and its inverse has a negative sign in the exponent. It is implemented with $O(n^2)$ gates: Hadamards, controlled phase gates and SWAP gates. It is used in phase estimation and Shor's algorithm. Note: some references define it with the opposite sign in the exponent.

Example

$n=2$, $x=2$: the amplitudes are $\tfrac12e^{2\pi i\cdot2y/4}=\tfrac12(-1)^y$, i.e. $\tfrac12(|0\rangle-|1\rangle+|2\rangle-|3\rangle)$. In Qiskit ordering this is $|+\rangle_{q_1}\otimes|-\rangle_{q_0}$ (verified) (the sign follows bit $q_0$).

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