Quantum Fourier transform

The quantum Fourier transform is the discrete Fourier transform with a particular decomposition into a product of simpler unitary matrices. Using this decomposition, the discrete Fourier transform can be implemented as a quantum circuit consisting of Hadamard gates and controlled phase shift gates.

The quantum Fourier transform has many applications in quantum algorithms as it provides the theoretical basis to the "phase estimation" procedure. This procedure is the key to quantum algorithms such as Shor's algorithm for factoring a number, the "order finding" algorithm and the "hidden subgroup" problem.

Details

"l"²(Z/("N")) is the Hilbert space of complex-valued functions on Z/"N" with the inner product

:$langle\; psi\; |\; phi\; angle\; =\; sum\_\{k\; in\; mathbb\{Z\}/(N)\}\; overline\{psi(k)\}\; phi(k)$

Recall that the discrete Fourier transform is a unitary mapping

: $ell^2(mathbb\{Z\}/(N))\; ightarrow\; ell^2(mathbb\{Z\}/(N)).$

given as follows. Let

:$|0\; angle,\; ldots,\; |N-1\; angle,$

be an orthonormal basis for "l"²(Z/("N")). The discrete Fourier transform on that basis is a linear operator with the following action on the basis states:

:$|j\; angle\; mapsto\; frac\{1\}\{sqrt\{Nsum\_\{k=0\}^\{N-1\}\; e^\{2\; pi\; i\; jk/N\}|k\; angle$

Alternatively, we can express this operator by the square matrix of size "N" whose entries are

:

The unitarity of this mapping can be checked directly.

The main point of the quantum Fourier transform is that in case "N" is a power of 2, this operator can be represented as a product. Suppose "N" = 2^"n". We have the orthonormal basis for "l"²(Z/("N")) consisting of the ket vectors indexed as follows

:$|0\; angle,\; ldots\; ,\; |2^n\; -\; 1\; angle.$

Each basis state index can be represented in binary form

:$|\; x\; angle\; =\; |\; x\_1,\; x\_2,\; ldots,\; x\_n\; angle\; =\; |\; x\_1\; angle\; otimes\; |\; x\_2\; angle\; otimes\; cdots\; otimes\; |\; x\_n\; angle$

where

:$x\; =\; x\_1\; 2^\{n-1\}\; +\; x\_2\; 2^\{n-2\}\; +cdots\; +\; x\_n\; 2^0.quad$

In the language of quantum computation, these are referred to as "computational basis states". (Each qubit, the basic unit of quantum information, resides in a two-dimensional Hilbert space and these basis states span the state space of a "n"-qubit composite system.)

We associate to such an integer "x" in the interval {0,1, ..., 2^"N" - 1} the rational number in the interval [0,1] whose binary representation is

:$[.\; x\_1\; ldots\; x\_n]\; =\; sum\_\{k\; =\; 1\}^n\; x\_k\; 2^\{-k\}\; quad$

Dot means::$frac\{x\_1\}\{2\}\; ightarrow\; (.x\_1)$:$frac\{x\_1\}\{2\}+frac\{x\_2\}\{2^2\}\; ightarrow\; (.x\_1\; x\_2)$:$frac\{x\_1\}\{2\}+frac\{x\_2\}\{2^2\}+frac\{x\_3\}\{2^3\}\; ightarrow\; (.x\_1\; x\_2\; x\_3)$:$...$

Theorem. The discrete Fourier transform on the computational basis states has the following structure:It maps the computational basis state

:$|x\_1,\; x\_2,\; ldots,\; x\_n\; angle$

into the tensor product

:$2^\{-frac\{n\}\{2\; left(|0\; angle\; +\; e^\{2\; pi\; i\; ,\; [.x\_n]\; \}|1\; angle\; ight)\; otimes\; left(|0\; angle\; +\; e^\{2\; pi\; i\; ,\; [.x\_\{n-1\}\; x\_n]\; \}|1\; angle\; ight)\; otimes\; cdots\; otimes\; left(|0\; angle\; +\; e^\{2\; pi\; i\; ,\; [.x\_1\; x\_2\; ldots\; x\_n]\; \}|1\; angle\; ight).$

In other words, the discrete Fourier transform, an operation on "n"-qubits, can factored into the tensor product of "n" single-qubit operations, suggesting it is easily represented as a quantum circuit.

References

* Michael A. Nielsen and Isaac L. Chuang, "Quantum Computation and Quantum Information" (Cambridge, UK, 2000)

* 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)