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

Question

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?

Answer 1

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.