2022 Developer Survey is open! Take survey.

Tag Info

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.