# Prove that applying the QFT twice is equivalent to classical multiplication by $-1$ modulo $2^n$

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.

• Do the sum over $y$ (it's a sum of a geometric progression). You'll want to do two different cases: one where $x+z\equiv 0\text{ mod }2^n$ and all others. Mar 15 at 6:02
• Think of the elements of the double summation as being laid out on a grid, and you're adding up all the cells in the grid. Consider what happens if you add up first the columns then the rows, or first the rows then the columns, or first the diagonals and then the anti-diagonals. You'll find that one of them is easier than the others. An alternative trick is to realize that the QFT is its own transpose, so QFT = sum_k |k><frequency_k| = sum_k conj(|frequency_k><k|) and so all you gotta do is resolve the conjugate and then decompose the two QFTs so the frequency parts meet on the inside. Mar 15 at 6:32
• @DaftWullie I do not understand how to use geometric progression for this problem. Like what will be the common ratio. Also, how can we sure that the common ratio is not equal to 1. Mar 16 at 1:35

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