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 amplitudes can be implemented as a quantum circuit consisting of only Hadamard gates and controlled phase shift gates, where is the number of qubits. This can be compared with the classical discrete Fourier transform, which takes gates (where is the number of bits), which is exponentially more than . 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 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. The classical (unitary) Fourier transform acts on a vector (x0, ..., xN−1) in and maps it to the vector (y0, ..., yN−1) according to the formula
Similarly, the quantum Fourier transform acts on a quantum state and maps it to a quantum state according to the formula:
with defined as above.
This can also be expressed as the map
Equivalently, the quantum Fourier transform can be viewed as a unitary matrix (quantum gate, similar to a logic gate for classical computers) acting on quantum state vectors, where the unitary matrix is given by
Here is a primitive Nthroot of unity. For example, in the case of we would find that , so
Most of the properties of the quantum Fourier transform follow from the fact that it is a unitary transformation. This can be checked by performing matrix multiplication and ensuring that the relation holds, where is the Hermitian adjoint of . Alternately, one can check that vectors of norm 1 get mapped to vectors of norm 1.
From the unitary property it follows that the inverse of the quantum Fourier transform is the Hermitian adjoint of the Fourier matrix, thus . Since there is an efficient quantum circuit implementing the quantum Fourier transform, the circuit can be run in reverse to perform the inverse quantum Fourier transform. Thus both transforms can be efficiently performed on a quantum computer.
The quantum Fourier transform can be approximately implemented for any N; however, the implementation for the case where N is a power of 2 is much simpler. Suppose N = 2n. We have the orthonormal basis consisting of the vectors
The basis states enumerate all the possible states of the qubits:
where, with tensor product notation , indicates that qubit is in state , with either 0 or 1. By convention, the basis state index orders the possible states of the qubits lexicographically, i.e., by converting from binary to decimal in this way:
It is also useful to borrow fractional binary notation:
For instance, and
With this notation, the action of the quantum Fourier transform can be expressed as:
where the output qubit 1 is in a superposition of state and , and so on for the other qubits.
In other words, the discrete Fourier transform, an operation on n-qubits, can be factored into the tensor product of n single-qubit operations, suggesting it is easily represented as a quantum circuit. In fact, each of those single-qubit operations can be implemented efficiently using a Hadamard gate and controlledphase gates. The first term requires one Hadamard gate, the next one requires a Hadamard gate and a controlled phase gate, and each following term requires an additional controlled phase gate. Summing up the number of gates gives gates, which is polynomial in the number of qubits.
^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 (pdf)
K. R. Parthasarathy, Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, June 2001)
John Preskill, Lecture Notes for Physics 229: Quantum Information and Computation (CIT, September 1998)