# Simon's Algorithm: Calculating the effects on the second Hadamard gate and the resulting amplitudes

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?

Your mistake happens at the step "we write the sum as one", the normalization term ought to be $$\dfrac{1}{\sqrt{2}\sqrt{2^n}}=\dfrac{1}{\sqrt{2^{n+1}}}$$, not $$\dfrac{1}{\sqrt{2^{n-1}}}$$.
Thus, the final state is: \begin{align*} \frac{2}{\sqrt{2^{n+1}}}\sum_{\{z|z\cdot s=0\}}(-1)^{x\cdot z}|z\rangle=\frac{1}{\sqrt{2^{n-1}}}\sum_{\{z|z\cdot s=0\}}(-1)^{x\cdot z}|z\rangle \end{align*}