Content deleted Content added
Bender2k14 (talk | contribs) added External links sections with a link to a Wolfram demonstration of the QFT |
Added disambiguation to the introduction: Quantum Fourier transform is faster because 2^n amplitudes take O(n^2) gates. |
||
Line 1:
In [[quantum computing]], the '''quantum Fourier transform''' is a [[linear transformation]] on [[qubit|quantum bits]], and is the quantum analogue of the [[discrete Fourier transform]]. The quantum Fourier transform is a part of many [[quantum algorithms]], notably [[Shor's algorithm]] for factoring and computing the [[discrete logarithm]], the [[quantum phase estimation algorithm]] for estimating the [[eigenvalue]]s of a [[unitary operator]], and algorithms for the [[hidden subgroup problem]].
The quantum Fourier transform can be performed efficiently on a quantum computer, with a particular decomposition into a product of simpler [[unitary matrix|unitary matrices]]. Using a simple decomposition, the discrete Fourier transform on <math>2^n</math> amplitudes can be implemented as a [[quantum circuit]] consisting of only <math>O(n^2)</math> [[Hadamard gate]]s and controlled [[phase shift gate]]s, where <math>n</math> is the number of qubits.<ref>{{cite book | author= [[Michael Nielsen]] and Isaac Chuang | title=Quantum Computation and Quantum Information | publisher=Cambridge University Press | ___location=Cambridge | year=2000 | isbn=0-521-63503-9 | oclc= 174527496}}</ref> This can be compared with the classical discrete Fourier transform, which takes <math>O(n2^n)</math> gates (where <math>n</math> is the number of bits), which is exponentially more than <math>O(n^2)</math>. However, the quantum Fourier transform acts on a quantum state, whereas the classical Fourier transform acts on a vector, so not every task that uses the classical Fourier transform can take advantage of this exponential speedup.
The best quantum Fourier transform algorithms known today require only <math>O(n \log n)</math> gates to achieve an efficient approximation.<ref>L. Hales, S. Hallgren, An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p. 515, November 12–14, 2000</ref>
| |||