Quantum Fourier transform: Difference between revisions

Revision as of 15:27, 21 August 2015

Revision as of 02:49, 26 January 2016

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 partone 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.