Proving $\frac{1}{2^n}\sum_{z\in\{0,1\}^n} (-1)^{z\cdot (x\oplus y)}=\delta_{xy}$, where $x\oplus y$ is the bitwise sum In quantum algorithms I often find this identity: $$\frac{1}{2^n}\sum_{z\in\{0,1\}^n} (-1)^{z\cdot (x\oplus y)}=\delta_{xy}$$ where $x\oplus y$ is the bitwise sum.
I am not able to prove in general the case in which $x\neq y$, I can only show that it works for particular sets (e.g. $\{0,1\}^2$, $\{0,1\}^3$).
 A: 
I am not able to prove in general the case in which $x\ne y$

Suppose $x\ne y$, and let $a:=x\oplus y.$ Then $a$ has a leftmost $1$-bit, say in position $p$. For any $z$ whose $p$th bit is $1$ (i.e. matching $a$ at that bit), let $f_a(z)$ be the result of flipping that bit in $z$ (so as to not match $a$ at that bit). Now, among the $2^n$ $z$ values, exactly half of them match the leftmost $1$-bit of $a$ and half do not; furthermore, $z\cdot a$ and $f_a(z)\cdot a$ have opposite parity, hence
$$\begin{align}\sum_{z\in\{0,1\}^n} (-1)^{z\cdot a}&=\sum_{z\in\{0,1\}^n:\text{$z$ matches the leftmost $1$-bit in $a$}} \left((-1)^{z\cdot a}+(-1)^{f_a(z)\cdot a}\right)=0.
\end{align}$$
A: As mentioned in the comments, the key is to distribute and distribute and distribute:
\begin{align}
\frac{1}{2^n}\sum_{z\in\{0,1\}^n} (-1)^{z\cdot (x\oplus y)}
& =
\frac{1}{2^n}\sum_{z\in\{0,1\}^n} 
(-1)^{\sum_i z_i(x_i\oplus y_i)}
\\ & =
\frac{1}{2\stackrel{n}{\cdots}2}
\sum_{z_1\in\{0,1\}} \cdots \sum_{z_n\in\{0,1\}} 
(-1)^{z_1(x_1\oplus y_1)} \cdots (-1)^{z_n(x_n\oplus y_n)}
\\ &  =
\left(
\frac12
\sum_{z_1\in\{0,1\}} 
(-1)^{z_1(x_1\oplus y_1)}
\right)
\cdots
\left(
\frac12
\sum_{z_n\in\{0,1\}} 
(-1)^{z_n(x_n\oplus y_n)}
\right)
\end{align}
In other words, the problem reduces to a product of copies of the $n=1$ case, which you've solved already.
