Skip to main content

Quantum Fourier Transform (QFT) is a linear transformation on quantum bits and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. (Wikipedia)

The quantum Fourier transform on an orthonormal basis $|0\rangle,...,|N-1\rangle$ is defined to be a linear operator with the following action on the basis states,

$$|j\rangle \longrightarrow \frac{1}{\sqrt{N}}\sum^{N-1}_{k=0}e^{2\pi ijk/N}|k\rangle.$$

Equivalently, the action on an arbitrary state may be written

$$\sum^{N-1}_{j=0} x_j |j\rangle \longrightarrow \sum^{N-1}_{k=0} y_k|k\rangle,$$

where the amplitudes $y_k$ are the discrete Fourier transform of the amplitudes $x_j$. The QFT is a unitary transformation, and thus can be implemented as the dynamics for a quantum computer.