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. The quantum Fourier transform was invented by Don Coppersmith.
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 formula_1 amplitudes can be implemented as a quantum circuit consisting of only formula_2 Hadamard gates and controlled phase shift gates, where formula_3 is the number of qubits. This can be compared with the classical discrete Fourier transform, which takes formula_4 gates (where formula_3 is the number of bits), which is exponentially more than formula_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 formula_7 gates to achieve an efficient approximation.
Definition.
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 formula_8.
The classical Fourier transform acts on a vector formula_9 and maps it to the vector
formula_10 according to the formula:
where formula_12 and formula_13 is an "N"th root of unity.
Similarly, the quantum Fourier transform acts on a quantum state formula_14 and maps it to a quantum state formula_15 according to the formula:
Since formula_13 is a rotation, the inverse quantum Fourier transform acts similarly but with:
In case that formula_19 is a basis state, the quantum Fourier Transform can also be expressed as the map
Equivalently, the quantum Fourier transform can be viewed as a unitary matrix (or a quantum gate, similar to a Boolean logic gate for classical computers) acting on quantum state vectors, where the unitary matrix formula_21 is given by
where formula_23. We get, for example, in the case of formula_24 and phase formula_25 the transformation matrix
Properties.
Unitarity.
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 formula_27 holds, where formula_28 is the Hermitian adjoint of formula_29. Alternately, one can check that orthogonal vectors of norm 1 get mapped to orthogonal 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 formula_30. 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.
Circuit implementation.
The quantum gates used in the circuit are the Hadamard gate and the controlled phase gate formula_31, here in terms of
with formula_33 the primitive formula_34-th root of unity. The circuit is composed of formula_35 gates and the controlled version of formula_31
All quantum operations must be linear, so it suffices to describe the function on each one of the basis states and let the mixed states be defined by linearity. This is in contrast to how Fourier transforms are usually described. We normally describe Fourier transforms in terms of how the components of the results are calculated on an arbitrary input. This is how you would calculate the path integral or show BQP is in PP. But it is much simpler here (and in many cases) to just explain what happens to a specific arbitrary basis state, and the total result can be found by linearity.
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. As already stated, we assume formula_8. 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 formula_40, formula_41 indicates that qubit formula_42 is in state formula_43, with formula_43 either 0 or 1. By convention, the basis state index formula_45 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, formula_48 and formula_49
With this notation, the action of the quantum Fourier transform can be expressed in a compact manner:
or
where we have used:
This can be seen by rewriting the formula for the Fourier transform in the binary expansion:
Now:
It could be simplified further by using formula_60, formula_61 and formula_62
and then even more given that formula_63, formula_64 and formula_65.
The 3-qubit quantum Fourier transform can be rewritten as:
or
In case that we use the circuit we obtain the factorization in reverse order, namely
Here we have used notations like:
In the following sketch, we have the respective circuit for formula_71 (with wrong order of output qubits with respect to the proper QFT):
As calculated above, the number of gates used is formula_72 which is equal to formula_73, for formula_71.
Relation to quantum Hadamard transform.
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 formula_75. However, it also makes sense to consider the qubits as indexed by the Boolean group formula_76, and in this case the Fourier transform is the Hadamard transform. This is achieved by applying a Hadamard gate to each of the n qubits in parallel. Note that Shor's algorithm uses both types of Fourier transforms, both an initial Hadamard transform as well as a QFT.