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:

    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)

    ... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.
    Adrienne Rich (b. 1929)

    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)