2

While going through the answer given on this post, I came across the sentence:

If you apply the $QFT$ twice, it is equivalent to a classical multiplication by -1 modulo $2^n$ where $n$ is the size of the register. That is to say, it reverses the order of all of the >computational basis states except for $\left|0\right>$ which stays where it started. $\left|k\right>$ becomes $\left|-k\right>=\left|2n-k\right>$.

I was trying to prove it using the following: $$ QFT \left|x\right> = \frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}e^{2\pi i xy/2^n}\left|y\right> $$

At most I was able to go to the following step: $$ (QFT)(QFT)\left|x\right> = \frac{1}{2^n}\sum_{y=0}^{2^n-1}\sum_{z=0}^{2^n-1}e^{2\pi i y(x+z)/2^n}\left|z\right>. $$ I am not sure if what I got is correct or not, but if it is correct, I do not know how to move forward and simplify the double summation to get something like the rule mentioned above. Any help will be appreciated so that I can solve it forward. I really need this kind of practice because I get scared of summation signs in such theorems easily.

glS
  • 27,510
  • 7
  • 37
  • 125
Srijan
  • 43
  • 5

1 Answers1

3

You have the term $$ \frac{1}{2^n}\sum_y\sum_z e^{2\pi iy(x+z)/2^n}|z\rangle. $$ I want to perform the sum over $y$: $$ \sum_y e^{2\pi iy(x+z)/2^n}. $$ This is just the sum of a geometric progression $\sum_{y=0}^{2^n-1}a^y$ for $a=e^{2\pi i(x+z)/2^n}$. Thus, we have $$ \sum_{y=0}^{2^n-1}a^y=\left\{\begin{array}{cc} \frac{1-a^{2^n}}{1-a} & a\neq 1 \\ 2^n & a=1 \end{array}\right. $$ So, $a=1$ if $x+z\equiv 0\text{ mod }2^n$. Thus, the amplitude of the term $z$ for which $x+z\equiv 0\text{ mod }2^n$ is 1. That already means all the other amplitudes must be 0 by normalisation, but let's check: $$ a^{2^n}=e^{2\pi i(x+z)}=1 $$ So $$ \sum_y e^{2\pi iy(x+z)/2^n}=\frac{1-1}{1-a}=0. $$

Hence, you always get the answer $z=2^n-x$.

DaftWullie
  • 62,671
  • 4
  • 55
  • 140