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 was discovered by Don Coppersmith.
[1] With small modifications to the QFT, it can also be used for performing fast integer arithmetic operations such as addition and multiplication.
[2][3][4] The quantum Fourier transform can be performed efficiently on a quantum computer with a decomposition into the product of simpler unitary matrices.
amplitudes can be implemented as a quantum circuit consisting of only
[5] This can be compared with the classical discrete Fourier transform, which takes
Both types of vectors can be written as lists of complex numbers.
In the classical case, the vector can be represented with e.g. an array of floating-point numbers, and in the quantum case it is a sequence of probability amplitudes for all the possible outcomes upon measurement (the outcomes are the basis states, or eigenstates).
Because measurement collapses the quantum state to a single basis state, not every task that uses the classical Fourier transform can take advantage of the quantum Fourier transform's exponential speedup.
The best quantum Fourier transform algorithms known (as of late 2000) require only
[6] The quantum Fourier transform is the classical discrete Fourier transform applied to the vector of amplitudes of a quantum state, which has length
The classical Fourier transform acts on a vector
according to the formula (Conventions for the sign of the phase factor exponent vary; here the quantum Fourier transform has the same effect as the inverse discrete Fourier transform, and conversely.)
is a rotation, the inverse quantum Fourier transform acts similarly but with In case that
This can be checked by performing matrix multiplication and ensuring that the relation
Thus both transforms can be efficiently performed on a quantum computer.
The quantum Fourier transform can be written as the tensor product of a series of terms: Using the fractional binary notation the action of the quantum Fourier transform can be expressed in a compact manner: To obtain this state from the circuit depicted above, a swap operation of the qubits must be performed to reverse their order.
[5] Because the discrete Fourier transform, an operation on n qubits, can be factored into the tensor product of n single-qubit operations, it is easily represented as a quantum circuit (up to an order reversal of the output).
Summing up the number of gates, excluding the ones needed for the output reversal, gives
gates, which is quadratic polynomial in the number of qubits.
[7] The circuit-level implementation of the quantum Fourier transform on a linear nearest neighbor architecture has been studied before.
[8][9] The circuit depth is linear in the number of qubits.
The matrix representation of the Fourier transform on three qubits is: The 3-qubit quantum Fourier transform can be rewritten as: The following sketch shows the respective circuit for
(with reversed order of output qubits with respect to the proper QFT):
Using the generalized Fourier transform on finite (abelian) groups, there are actually two natural ways to define a quantum Fourier transform on an n-qubit quantum register.
The QFT as defined above is equivalent to the DFT, which considers these n qubits as indexed by the cyclic group
However, it also makes sense to consider the qubits as indexed by the Boolean group
This is achieved by applying a Hadamard gate to each of the n qubits in parallel.
[13][14] The Fourier transform can be expressed in matrix form where
The discrete Fourier transform can also be formulated over a finite field