I have some problems in solving exercise 6.5.1 of Mosca's book "Introduction to quantum computation". The statement is very very easy.

Let $x,y \in \{0,1\}^n$ and let $s=x \oplus y$. Show that:

$$H^{\otimes n} (\frac{1}{\sqrt{2}}|x\rangle+\frac{1}{\sqrt{2}} |y\rangle) = \frac{1}{\sqrt{2^{n-1}}} \sum_{i \in {s^\perp}}|i\rangle$$

Where $H^{\otimes n}$ is the Hadamard tensored with itself $n$ times..

These are my calculations: $$\frac{1}{\sqrt{2}} \left( \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{xi}|i\rangle \right) + \left( \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{yi}|i\rangle \right)$$

$$\frac{1}{\sqrt{2}} \left( \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{xi}|i\rangle \right) + \left( \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} (-1)^{(s \oplus x)i}|i\rangle \right)$$

$$\frac{1}{\sqrt{2}} \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} \left( (-1)^{xi} + (-1)^{(s \oplus x)i} \right)|i\rangle$$

$$\frac{1}{\sqrt{2^{n+1}}} \sum_{i=0}^{2^n-1} \left((-1)^{xi} + (-1)^{xi \oplus si} \right)|i\rangle$$

factoring out $(-1)^{xi}$:

$$\frac{1}{\sqrt{2^{n+1}}} \sum_{i=0}^{2^n-1} \left(1 + (-1)^{si} \right)(-1)^{xi}|i\rangle$$

Here we can clearly see that for basis vector such that si=1 we got interference, and the amplitude of that base is $0= (1+(-1)^1)$.

But then? Am I good so far?

Perhaps I'm getting confused by the fact that the scalar product at the exponent is in $Z_2^n$. It should be defined as $<z,i> = z_1 \land i_1 \oplus ... \oplus z_n \land i_n = (z_1 \land i_1 + ... + z_n \land i_n) mod 2$

$Z_2^n$ is a very weird space. What is it's name? What are it's property? It makes me think of a ring of polynomials of length n over the binary field, but of course this is a space and not a ring.

Also I don't even imagine how I can get from $\frac{1}{\sqrt{2^{n+1}}}$ to $\frac{1}{\sqrt{2^{n-1}}}$

Please don't give me the solution, but just a hint, or please tell me the operation that i need to study in order to apply it to the next step.

Thanks.

• 1. You have not given the form of $H$. 2. The scalar product is not "in $\mathbb{Z}_2^n$". Your labels are in that space, the actual states and their scalar product are in $(\mathbb{C}^2)^{\otimes n}$. – ACuriousMind Jan 18 '17 at 18:07