Quantum Fourier Transform

$QFT|x\rangle = \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1} e^{\frac{2\pi i}{N} xy} |y\rangle$

Let $\omega = e^\frac{2\pi i}{N}$, then $QFT|x\rangle = \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1} \omega^{xy} |y\rangle$.

Note that $\sum_{n=0}^{N-1} a^n = \begin{cases}N \text{ for } a = 1\\ \frac{a^{N} - 1}{a - 1} \text{ for } a \not= 1 \end{cases}$

Note that $\omega^k = 1$ iff. $N|k$,

Thus if $N|k$, $\sum_{n=0}^{N-1} \omega^{kn} = N$. and if $N\not|k$, $\sum_{n=0}^{N-1} \omega^{kn} = \frac{\omega^{kN} - 1}{\omega^k - 1} = 0$.