Quantum Fourier transform

In quantum computing, the quantum Fourier transform 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.

The quantum Fourier transform can be performed efficiently on a quantum computer, with a particular decomposition into a product of simpler unitary matrices. Using a simple decomposition, the discrete Fourier transform on ${\displaystyle 2^{n}}$ amplitudes can be implemented as a quantum circuit consisting of only ${\displaystyle O(n^{2})}$ Hadamard gates and controlled phase shift gates, where ${\displaystyle n}$ is the number of qubits. This can be compared with the classical discrete Fourier transform, which takes ${\displaystyle O(n2^{n})}$ gates (where ${\displaystyle n}$ is the number of bits), which is exponentially more than ${\displaystyle O(n^{2})}$. However, the quantum Fourier transform acts on a quantum state, whereas the classical Fourier transform acts on a vector, so not every task that uses the classical Fourier transform can take advantage of this exponential speedup.

...
Wikipedia