nLab quantum Fourier transform

Idea

The quantum Fourier transform (QFT) is an analog of the discrete Fourier transform, acting on quantum states.

The QFT is a crucial ingredient in several quantum algorithms, notably in Shor's algorithm.

Nominally, the QFT on an $n$-dimensional Hilbert space requires only $\mathcal{O}(n^2)$ quantum gates, as opposed to the $\mathcal{O}(n 2^n)$ logic gates for the classical discrete Fourier transform on $n$-dimensional vectors. However, this nominal speedup is not practically extractable for computation of Fourier transforms, since classical en- and de-coding of the data for the QFT is impractical: the Fourier transformed vector is in the complex phases of the coefficients of the output quantum state, which are not directly measurable. [Nielsen & Chuang 2000 p 220].

However there are practically accessible quantum algorithms with quantum advantage which rely the QFT as a sub-routine, notably “quantum phase estimation” [NC00 §5.2] (used, in turn, in Shor's algorithm).

Related concepts

• Fourier transform

• Shor's algorithm

• rotation gate

References

Textbook account:

• Michael A. Nielsen, Isaac L. Chuang, chapter 5 in: Quantum computation and quantum information, Cambridge University Press (2000) [doi:10.1017/CBO9780511976667, pdf, pdf]

See also:

• Wikipedia: Quantum Fourier Transform

Generalization of the QFT algorithm from qbits to a platform of qdits:

• Ashok Muthukrishnan, C. R. Stroud Jr: Quantum fast Fourier transform using multilevel atoms, Journal of Modern Optics 49 13 (2002) [arXiv:quant-ph/0112017, doi:10.1080/09500340210123947]

• Zeljko Zilic, Katarzyna Radecka: Scaling and better approximating quantum Fourier transform by higher radices, IEEE Transactions on Computers 56 2 (2007) 202-207 [arXiv:quant-ph/0702195, doi:10.1109/TC.2007.35]

• Cao Ye et al.: Quantum Fourier Transform and Phase Estimation in Qudit System, Commun. Theor. Phys. 55 790 (2011) [doi:10.1088/0253-6102/55/5/11]

Review of the qdit formulation:

• Yuchen Wang, Zixuan Hu, Barry C. Sanders, Sabre Kais, section 3.2.1 of: Qudits and high-dimensional quantum computing, Front. Phys. 8 479 (2020) [arXiv:2008.00959, doi:10.3389/fphy.2020.589504]