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

:$$frac{1}{sqrt{N egin{bmatrix} omega^{k ell} end{bmatrix}, quad omega = e^{2 pi i /N}

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)