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?


1 Answer 1


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*} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.