Is QFT really faster FFT?

Question

The standard DFT:

$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2 \pi kn/N} \tag{1}$$

takes approximately $N^2$ complex summations and multiplications (or $\mathcal{O}(N^2)$). The faster version of FT known as FFT is extermely faster than the classical DFT and requires approximately $Nlog_2N$ complex summations and multiplications (or $\mathcal{O}(Nlog_2N)$) through butterfly structures and less calculations of twiddle factors. For QFT I just know that it operates with the phases in Fourier basis, so the result of such transform is the rotation of each qubit for the angle, which is factor of 2 more or less realtive to the neghboring qubit:

$$QFT_N|x\rangle = \frac{1}{\sqrt(N)} \left(|0\rangle+e^{\frac{2\pi i}{2}x}|1\rangle\right)\otimes \left(|0\rangle+e^{\frac{2\pi i}{2^2}x}|1\rangle\right)\otimes...\otimes\left(|0\rangle+e^{\frac{2\pi i}{2^{n-1}}x}|1\rangle\right)\otimes\left(|0\rangle+e^{\frac{2\pi i}{2^{n}}x}|1\rangle\right)\tag{2}$$

In this case for me it is not evident how to calculate the complexity of this algorithm. How can I estimate the complexity of QFT in terms of complex summations and multiplications?

Answer 1

You're doing the Fourier transform over a basis of size $N$. If we assume that $N=2^n$, then you're using $n=\log_2(N)$ qubits in the quantum algorithm.

You can look up what the circuit looks like for the QFT. The key ingredient is that there's a controlled-phase gate (of some phase) between every pair of qubits. Overall, there are $O(n^2)$ gates. This is your complexity.