Quantum Fourier Transform - Definition

Definition

The quantum Fourier transform is the classical discrete Fourier transform applied to the vector of amplitudes of a quantum state. The classical (unitary) Fourier transform acts on a vector in, (x0, ..., xN−1) and maps it to the vector (y0, ..., yN−1) according to the formula:

where is a primitive Nth root of unity.

Similarly, the quantum Fourier transform acts on a quantum state and maps it to a quantum state according to the formula:

.

This can also be expressed as the map

.

Equivalently, the quantum Fourier transform can be viewed as a unitary matrix acting on quantum state vectors, where the unitary matrix is given by


F_N = \frac{1}{\sqrt{N}} \begin{bmatrix}
1&1&1&1&\cdots &1 \\
1&\omega&\omega^2&\omega^3&\cdots&\omega^{N-1} \\
1&\omega^2&\omega^4&\omega^6&\cdots&\omega^{2(N-1)}\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^{3(N-1)}\\
\vdots&\vdots&\vdots&\vdots&&\vdots\\
1&\omega^{N-1}&\omega^{2(N-1)}&\omega^{3(N-1)}&\cdots&\omega^{(N-1)(N-1)}\\
\end{bmatrix}
.

Read more about this topic:  Quantum Fourier Transform

Famous quotes containing the word definition:

    Scientific method is the way to truth, but it affords, even in
    principle, no unique definition of truth. Any so-called pragmatic
    definition of truth is doomed to failure equally.
    Willard Van Orman Quine (b. 1908)

    Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.
    Nadine Gordimer (b. 1923)

    I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.”
    Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)