# What is the output of applying the Hadamard matrix to $\sum_{y\in\{0,1\}^n} (-1)^{xy}|y\rangle$?

If, for some $$x$$, I have the $$n$$-qubit state $$\sum_{y\in\{0,1\}^n} (-1)^{xy}|y\rangle,$$ and I would like to apply to that the $$n$$-qubit Hadamard transform, with the aim of calculating the final state.

I understand I can continue like following: $$\sum_{y\in\{0,1\}^n}\sum_{j\in\{0,1\}^n}(-1)^{xy}(-1)^{jy} |j\rangle = \sum_{y\in\{0,1\}^n}\sum_{j\in\{0,1\}^n}(-1)^{y(x+j)}|j\rangle,$$ but what cancels out here and why?

• Why is this getting downvoted? – Attila Kun Sep 8 '20 at 12:17
• including text/math in figures is generally frowned upon – glS Sep 8 '20 at 12:26
• How are you editing your math equation? – Ido Sep 8 '20 at 13:06
• @Ido you can see the source of your question by clicking on "edit". Math is added using mathjax. Also, you need to tag people using @name to make sure they get notified of your comment – glS Sep 8 '20 at 14:44
• @glS thank you! – Ido Sep 9 '20 at 6:56

Use the identity $$\sum_{y\in\{0,1\}^n} (-1)^{y\cdot z} = 2^n \delta_{z,0}$$ with $$z=x+j$$. This identity is based on the fact that "summing $$d$$-th roots of unity gives zero" if $$d>1$$.

Then you see that the result of applying the Hadamard gate twice is indeed the input state: $$\sum_{y\in\{0,1\}^n} \sum_{j\in\{0,1\}^n} (-1)^{y\cdot (x+j)} |j\rangle = 2^n |x\rangle$$ Note that usually the Hadamard gate is normalised by $$2^{-n/2}$$ for it to be unitary.

Remark: In higher-dimensional systems, $$H\neq H^{-1}$$, which you can see above since the identity would give you $$j=-x$$ which is only equal to $$x$$ in $$\mathbb{Z}_2=\{0,1\}$$. There, the inverse has an additional minus sign in the exponent (well, and replace $$-1$$ by $$e^{2\pi i/d}$$).

EDIT: I was asked to elaborate on the sum of roots of unity. Let's show the following $$\sum_{y\in\mathbb{Z}_d^n} \omega^{y\cdot z} = d^n \delta_{z,0},$$ where $$d>1$$ and $$\omega$$ is primitive $$d$$-th root of unity, e.g. $$\omega=e^{2\pi i/d}$$. Above, we have $$d=2$$. We have the following identity for the sum of all primitive $$d$$-th roots: $$\sum_{k=0}^{d-1} \omega^k = 0.$$ I will not give a proof of this. It should be clear from the geometrical intuition, just think about the equidistant position of the roots of unity on the unit circle (cp. Wiki). Next, we have to count how many times we get each root of unity in the second-to-last equation. If $$z\neq 0$$, there are $$d^{n-1}$$ possible solutions $$y\in\mathbb{Z}_d^n$$ to each of the linear systems $$y\cdot z = k$$ for $$k\in\mathbb{Z}_d$$. Clearly, the solution spaces are mutally disjoint and their union is $$\mathbb{Z}_d^n$$. Thus, any primitive root appears exactly $$d^{n-1}$$ times, and the sum is $$d^{n-1} \sum_{k=0}^{d-1} \omega^k = 0$$. If $$z=0$$, however, any term is identically $$1$$ and the result is $$d^n$$.

PS: BTW, the matrix representation of the Hadamard gate is just the discrete Fourier transform; the math is the same.

• Thank you! this helps so much. Can you please elaborate on why $$\sum_{y\in\{0,1\}^n} (-1)^{y\cdot z} = 2^n \delta_{z,0}$$ is correct? – Ido Sep 8 '20 at 7:13
• I expanded my answer. – Markus Heinrich Sep 8 '20 at 12:15
• Thank you so much! this is enormously helpful! – Ido Sep 8 '20 at 13:30