2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Try to draw the terms in the sum in the complex plane, it will be clear that they sum to $0$. For a proof see this question on Math SE $\endgroup$ – user2723984 Sep 1 at 17:56
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.