# Quantum Fourier transform
**Quantum Fourier transform** (QFT) is the quantum analogue of the discrete Fourier transform (DFT). It maps a computational basis state $\lvert j\rangle$ to a superposition whose amplitudes encode the DFT of the input amplitudes, for $N = 2^n$ states on $n$ qubits.

$$\text{QFT}\lvert j\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi ijk/N}\lvert k\rangle$$

The QFT is implemented in $O(n^2)$ gate operations on $n$ qubits, an exponential improvement over the classical fast Fourier transform which requires $O(N \log N) = O(n \cdot 2^n)$ operations. However, because measuring the output state collapses it to a single basis state, the QFT cannot be used to directly read out all DFT coefficients. Its power lies in its use as a subroutine within larger quantum algorithms.

## Circuit
The QFT circuit on $n$ qubits consists of a Hadamard gate followed by controlled phase rotations on each qubit, working from the most significant to the least significant, followed by SWAP gates to reverse the qubit order. The total gate count is $n(n+1)/2$ gates.

$$R_k = P\!\left(\frac{2\pi}{2^k}\right) = \begin{pmatrix}1 & 0 \\ 0 & e^{2\pi i/2^k}\end{pmatrix}$$

## Applications
The QFT is a central subroutine in quantum phase estimation ([[qpe]]), which itself is used in [[shor|Shor's factoring algorithm]] and the [[hhl|HHL algorithm]]. The inverse QFT is used to extract the period of a function, which is the core of Shor's approach to integer factorization.