Quantum Fourier transform

In quantum computing, the quantum Fourier transform (for short: QFT) is a linear transformation on quantum bits, and is the quantum analogue of the inverse 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 eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. In quantum computing, the quantum Fourier transform (for short: QFT) is a linear transformation on quantum bits, and is the quantum analogue of the inverse 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 eigenvalues 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 matrices. Using a simple decomposition, the discrete Fourier transform on 2 n {displaystyle 2^{n}} amplitudes can be implemented as a quantum circuit consisting of only O ( n 2 ) {displaystyle O(n^{2})} Hadamard gates and controlled phase shift gates, where n {displaystyle n} is the number of qubits. This can be compared with the classical discrete Fourier transform, which takes O ( n 2 n ) {displaystyle O(n2^{n})} gates (where n {displaystyle n} is the number of bits), which is exponentially more than O ( n 2 ) {displaystyle O(n^{2})} . 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 (as of late 2000) require only O ( n log ⁡ n ) {displaystyle O(nlog n)} gates to achieve an efficient approximation. The quantum Fourier transform is the classical discrete Fourier transform applied to the vector of amplitudes of a quantum state, where we usually consider vectors of length N := 2 n {displaystyle N:=2^{n}} . The classical Fourier transform acts on a vector ( x 0 , x 1 , … , x N − 1 ) ∈ C N {displaystyle (x_{0},x_{1},ldots ,x_{N-1})in mathbb {C} ^{N}} and maps it to the vector ( y 0 , y 1 , … , y N − 1 ) ∈ C N {displaystyle (y_{0},y_{1},ldots ,y_{N-1})in mathbb {C} ^{N}} according to the formula where ω n = e − 2 π n i N {displaystyle omega _{n}=e^{frac {-2pi ni}{N}}} is an Nth root of unity. Similarly, the quantum Fourier transform acts on a quantum state | x ⟩ = ∑ i = 0 N − 1 x i | i ⟩ {displaystyle |x angle =sum _{i=0}^{N-1}x_{i}|i angle } and maps it to a quantum state ∑ i = 0 N − 1 y i | i ⟩ {displaystyle sum _{i=0}^{N-1}y_{i}|i angle } according to the formula: where ω n = e − 2 π n i N {displaystyle omega _{n}=e^{frac {-2pi ni}{N}}} . Note that this is the inverse of the classical discrete Fourier transform; by convention, the quantum Fourier transform has the same effect as the inverse discrete Fourier transform, and vice versa. Since ω n {displaystyle omega _{n}} is a rotation, the inverse quantum Fourier transform acts similarly but with In case that | x ⟩ {displaystyle |x angle } is a basis state, the quantum Fourier Transform can also be expressed as the map