Quantum Fourier transform

From Wikipedia, the free encyclopedia

You have new messages (last change).

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

l2(Z/(N)) is the inner product 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 l2(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}

By the discrete Plancherel theorem, this mapping is a unitary transformation.

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 = 2n. We have the orthonormal basis for l2(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

| x \rangle = | x_1, x_2, \ldots, x_n \rangle = | x_1 \rangle \otimes | x_2 \rangle \otimes \cdots \otimes | x_n \rangle

where

x = x_1 2^{n-1} + \cdots + x_n 2^0.\quad

In the jargon of quantum computation, these are referred to as computational basis states.

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

[0. x_1 \ldots x_n] = \sum_{k = 1}^n x_k 2^{-k} \quad

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 \, [0.x_n] }|1\rangle\right) \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_{n-1} x_n] }|1\rangle\right) \otimes \cdots \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_1 x_2 \ldots x_n] }|1\rangle\right).

Given this fact, the discrete Fourier transform can be easily represented as a quantum circuit.

[edit] 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)
Retrieved from "http://en.wikipedia.org../../../q/u/a/Quantum_Fourier_transform_8098.html"
In other languages