Quantum Fourier Transform Definition
The discrete Fourier transform acting on the amplitudes of $n$ qubits.
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
- 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.
- 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
