I am currently reading about Simon's algorithm in "An Introduction to Quantum Computing" and stumbled over Exercise 6.5.1, that ask the reader to show that:
Let $\textbf{x}, \textbf{y} \in \{0,1\}^n$ and let $s = x \oplus y$. Show that $$H^{\otimes n} \left(\frac{1}{\sqrt{2}} |x⟩ + \frac{1}{\sqrt{2}} |y⟩ \right) = \frac{1}{\sqrt{2^{n-1}}} \sum_{\{z \mid z \cdot s = 0\} } (-1)^{x \cdot z} |z⟩$$
I think I am close to showing this, but my amplitudes are off -- what am I missing in the below derivation?
We know that $H^{\otimes n} |x⟩ = \frac{1}{\sqrt{2^n}}\sum_{z \in \{0,1\}^n} (-1)^{x \cdot z} |z⟩$
So we use that to derive: $$ H^{\otimes n} \left( \frac{1}{\sqrt{2}}|x⟩ + \frac{1}{\sqrt{2}} |y⟩ \right) = \frac{1}{\sqrt{2}} \left(H^{\otimes n} |x⟩ + H^{\otimes n} |y⟩\right)$$ $$ = \frac{1}{\sqrt{2}} \left(\frac{1}{\sqrt{2^n}}\sum_{z \in \{0,1\}^n} (-1)^{x \cdot z} |z⟩ + \frac{1}{\sqrt{2^n}}\sum_{z \in \{0,1\}^n} (-1)^{y \cdot z} |z⟩ \right) $$ We write the sum as one: $$ =\frac{1}{\sqrt{2^{n-1}}} \left (\sum_{z \in \{0,1\}^n} (-1)^{x \cdot z} |z⟩ + (-1)^{y \cdot z} |z⟩ \right) $$ We know use the fact that $y = x \oplus s$: $$ = \frac{1}{\sqrt{2^{n-1}}} \left( \sum_{z \in \{0,1\}^n} (-1)^{x \cdot z} |z⟩ + (-1)^{(x \oplus s) \cdot z} |z⟩ \right) $$ $$ = \frac{1}{\sqrt{2^{n-1}}} \left( \sum_{z \in \{0,1\}^n} (-1)^{x \cdot z} |z⟩ + (-1)^{(x \cdot z) \oplus (s \cdot z)} |z⟩ \right) $$ We write know that if $s \cdot z =1 $, the amplitudes cancel each other out, leaving only $$ = \frac{1}{\sqrt{2^{n-1}}} \left( \sum_{\{z \mid z \cdot s = 0\}} (-1)^{x \cdot z} |z⟩ + (-1)^{(x \cdot z)} |z⟩ \right)$$ This is where I am stuck -- This should leave each of the remaining states $|z⟩$ with amplitude $2 \cdot (-1)^{x \cdot z}$, right? But this not match the result in the book nor do the amplitudes sum to one: The vector subspace of $\mathbb{Z}^n_2$, $\{z \in \{0,1\}^n \mid s \cdot z = 0\}$ has dimension $n-1$ and thus contain $2^{n-1}$ vectors, right? So the amplitudes would not sum to one?
