Quantum Fourier Transform
Here we make use of this notation.
We define the quantum Fourier transform (QFT) as a $n$-qubit gate $\mathrm{QFT}$ such that:
$$ \mathrm{QFT} \ket{x}_n = \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^{n}-1} e^{2\pi i x y / 2^n} \ket{y}_n $$where $xy$ is the ordinary product. We will often omit the subscript $n$ in the computational basis.
Remark
- If $x \neq \bar{x}$, then $\mathrm{QFT}\ket{x}$ is orthogonal to $\mathrm{QFT}\ket{\bar{x}}$
- $\mathrm{QFT}\ket{x}$ is a normal vector for every $\ket{x}$ in the computational basis;
More on the QFT
For an arbitrary state $\sum_{x=0}^{2^n - 1} \gamma(x) \ket{x} $ , we have:
$$\mathrm{QFT} \left( \sum_{x=0}^{2^n - 1} \gamma(x) \ket{x} \right)=\sum_{x=0}^{2^n - 1} \tilde{\gamma}(x) \ket{x}$$where
$$\tilde{\gamma}(x) = \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n - 1} e^{2\pi i x y / 2^n} \gamma(y)$$are the discrete Fourier transform of the amplitudes $\gamma(x)$.
The Fast Fourier Transform (FFT) can be implemented with a $\mathcal{O}(N\log{N})$ time complexity, where $N$ is the length of the input vector or sequence. The QFT can be performed with a $\mathcal{O}(n^2)$ time complexity (i.e. number of elementary gates), where $n$ is the number of qubits. Since $n=\log{N}$, complexity can be written $\mathcal{O}((\log{N})^2)$: an exponential speed-up with respect to the FFT. Of course, one have to consider that the state obtained by the QFT is not determined, as it is for the FFT.