Quantum Fourier transform Guide, Meaning , Facts, Information and Description

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 inner product space of complex-valued functionss on Z/N with the inner product

Recall that the discrete Fourier transform is a unitary mapping

given as follows. Let

,

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:

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

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 = 2ⁿ. We have the orthonormal basis for l²(Z/(N)) consisting of the ket vectors indexed as follows

Each basis state index has can be represented in binary form

where

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, ..., 2^N - 1} the rational number in the interval [0,1] whose binary representation is

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

into the tensor product

Given this fact, the discrete Fourier transform can be 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)

This is an Article on Quantum Fourier transform. Page Contains Information, Facts Details or Explanation Guide About Quantum Fourier transform

	Web www.E-paranoids.com