Quantum Fourier transform

From Wikipedia, the free encyclopedia

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.

[edit] Details

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

$\langle \psi | \phi \rangle = \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)) \rightarrow \ell^2(\mathbb{Z}/(N)).$

given as follows. Let

$|0\rangle, \ldots, |N-1\rangle,$

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\rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2 \pi i \ jk/N}|k\rangle$

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

$\frac{1}{\sqrt{N}} \begin{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ⁿ. We have the orthonormal basis for l²(Z/(N)) consisting of the ket vectors indexed as follows

$|0\rangle, \ldots , |2^n - 1\rangle.$

Each basis state index can be represented in binary form

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} \rightarrow (.x_1)$

$\frac{x_1}{2}+\frac{x_2}{2^2} \rightarrow (.x_1 x_2)$

$\frac{x_1}{2}+\frac{x_2}{2^2}+\frac{x_3}{2^3} \rightarrow (.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 \rangle$

into the tensor product

$2^{-\frac{n}{2}} \ \left(|0\rangle + e^{2 \pi i \, [.x_n] }|1\rangle\right) \otimes \left(|0\rangle + e^{2 \pi i \, [.x_{n-1} x_n] }|1\rangle\right) \otimes \cdots \otimes \left(|0\rangle + e^{2 \pi i \, [.x_1 x_2 \ldots x_n] }|1\rangle\right).$

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.