Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I am trying to prove the following relation related to the Quantum Fourier Transform:
$$\sum_{y=0}^{N-1}e^{2\pi i\frac{x}{N}y} = \begin{cases}0 & \text{if } x\neq 0\mod N \\ N & \text{if } x=0\mod N\end{cases}.$$
I could not find the proof anywhere. What are the possible ways to proceed?
Let $f(y)=e^{2\pi i \frac{x}{N}y}, Y=\sum_{y=0}^{N-1}f(y)$. Clearly $f(0)=f(N)=1$.
If $x = 0\mod N$, then $f(y)=1$, hence $Y=N$.
If $x\not= 0 \mod N$, then $f(1)\not=1$. Now $f(1)Y=\sum_{y=1}^{N}f(x) = Y - f(0) + f(N) = Y$, so $Y(f(1)-1)=0$. Since $f(1)\not=1$, then $Y=0$.
The case of $x=0\text{ mod }N$ is straightforward - each term in the sum is $e^0=1$ and there are $N$ terms in the sum.
For $x\neq 0$, there are a number of ways you could do this. I tend to use the sum of a geometric progression: $$ \sum_{r=0}^{N-1}a^r=\frac{a^N-1}{a-1}, $$ assuming $a\neq 1$. Hence, if we let $a=e^{2\pi ix/N}$, the sum is $$ \frac{e^{2\pi ix}-1}{e^{2\pi ix/N}-1}=0. $$
