Showing that Hadamard is its own inverse

Question

Im trying to work out that a Hadamard transform H (a unitary matrix) is its own inverse by applying it twice to an arbitrary state $|x⟩$:

$$H|x⟩ = \frac{1}{\sqrt{2^n}}\sum_{y \in \{0,1\}^n}(-1)^{x \cdot y}|y⟩\,.$$

Then \begin{align*} H\left(\frac{1}{\sqrt{2^n}}\sum_{y \in \{0,1\}^n}(-1)^{x \cdot y}|y⟩\right) &= \frac{1}{2^n}\sum_{y \in \{0,1\}^n} (-1)^{x \cdot y}\sum_{z \in \{0,1\}^n}(-1)^{y \cdot z}|z⟩\\ &=\frac{1}{2^n}\sum_{y \in \{0,1\}^n}\sum_{z \in \{0,1\}^n} (-1)^{x \cdot y}(-1)^{y \cdot z}|z⟩\\ &= \frac{1}{2^n}\sum_{y \in \{0,1\}^n}\sum_{z \in \{0,1\}^n}(-1)^{y \cdot (x + z)}|z⟩\,. \end{align*}

But I don't know how to get from here to $|x⟩$ again.

I know that $HH^* = I$, but I want to show it this way, to understand what is happening.

Answer 1

Rewrite your final expression as $$ \sum_{z \in \{0,1\}^n} \left| z \right\rangle \cdot \frac{1}{2^n} \sum_{y \in \{0,1\}^n} (-1)^{y \cdot (x+z)}. $$ So to complete the proof, we need to show that $$ \sum_{y \in \{0,1\}^n} (-1)^{y \cdot (x+z)} = \begin{cases} 2^n & \text{if } x=z, \\ 0 & \text{otherwise}. \end{cases} $$ If $x=z$ then $x+z = 0$ (computing modulo 2!), and so $(-1)^{y \cdot (x+z)} = 1$ for all $y$, hence the sum equals $2^n$. If $x \neq z$ then pick some $i$ such that $x_i \neq z_i$. We can partition $y$ into the $i$th coordinate $y_i$ and all the rest $y_{-i}$. Now $$ \sum_{y \in \{0,1\}^n} (-1)^{y \cdot (x+z)} = \sum_{y_{-i} \in \{0,1\}^{n-1}} (-1)^{y_{-i} \cdot (x+z)_{-i}} \sum_{y_i \in \{0,1\}} (-1)^{y_i \cdot (x+z)_i} = 0, $$ since $x_i+z_i = 1$ (modulo 2) and $\sum_{y_i \in \{0,1\}} (-1)^{y_i} = 1-1=0$.