I'm having trouble understanding the notation used in a linear algebra exercise (it's exercise 2.33 of Nielsen and Chuang's "Quantum Computation and Quantum Information", page 74).
The exercise gives the Hadamard matrix
$$H = \frac{1}{\sqrt{2}} \Bigl[ (|0\rangle + |1\rangle)\langle 0| + (|0\rangle – |1\rangle)\langle 1| \Bigr]$$
and asks us to show that
$$H^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x,y} (-1)^{x \cdot y} |x \rangle \langle y|$$
My understanding is that $x$ and $y$ in the sum run through the basis vectors for the tensor product space, but my problem is that I don't understand what they're supposed to mean in the exponent of $(-1)$.
I thought I was supposed to interpret them in base $2$ ("$00$" as $0$, "$10$" as $2$, etc.), but then then the formula doesn't seem to work. For example, taking $n=2$ and computing the tensor product using the matrix representation of $H$:
$$H^{\otimes 2} = H \otimes H
= \frac{1}{2} \left[ \begin{array}{rr}
1 \left[ \begin{array}{rr} 1&1 \\ 1&-1 \end{array} \right] &
1 \left[ \begin{array}{rr} 1&1 \\ 1&-1 \end{array} \right] \\
1 \left[ \begin{array}{rr} 1&1 \\ 1&-1 \end{array} \right] &
-1 \left[ \begin{array}{rr} 1&1 \\ 1&-1 \end{array} \right]
\end{array} \right]
= \frac{1}{2} \left[ \begin{array}{rrrr}
1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 \\
1 & 1 & -1 & -1 \\
1 & -1 & -1 & 1
\end{array} \right]$$
But, from the formula given in the book (and my probably mistaken interpretation of $x$ and $y$), the coefficient at, say, $|10 \rangle \langle 10|$ should be $(-1)^{2 \cdot 2} = 1$, but the corresponding coefficient in the matrix is $-1$.
I feel I'm being dumb and missing something very simple, but I can't see it. What am I doing wrong?
Best Answer
Let's start by considering the base case of $n=1$, which is just $H$ itself:
$$H = \frac{1}{\sqrt{2}} \Bigl[ (|0\rangle + |1\rangle)\langle 0| + (|0\rangle - |1\rangle)\langle 1| \Bigr]=\frac{1}{\sqrt{2}}\Bigl[|0\rangle \langle 0|+|1\rangle \langle 0|+|0\rangle \langle 1|-|1\rangle \langle 1|\Bigr].$$
Comparing this with the formula $H^{\otimes 1} =H= \frac{1}{\sqrt{2}} \sum_{x,y} (-1)^{x \cdot y} |x \rangle \langle y|$, we see that only the $x=y=1$ case generates a minus sign. So it would seem that $x\cdot y=xy$ is enough for $n=1$.
As noted in the question, though, the meaning of $x \cdot y$ isn't obvious in the $n=2$ case. But observe that the tensor products which pick up a minus sign are
$$ |0\rangle \langle 0| \otimes |1\rangle \langle 1|,\, |0\rangle \langle 1| \otimes |1\rangle \langle 1|,\, |1\rangle \langle 0| \otimes |1\rangle \langle 1|,\, $$ as well as $$ |1\rangle\langle 1|\otimes|0\rangle\langle 0|,\, |1\rangle\langle 1|\otimes|1\rangle\langle 0|,\; \text{and} \; |1\rangle\langle 1|\otimes|0\rangle\langle 1| .$$ Each is tensored with a single $|1\rangle \langle 1|$ product, the same that carried the minus sign in $H$. On the other hand, the product $|1\rangle \langle 1|\otimes |1\rangle \langle 1|$ has a positive sign; this is natural, since $+1=(-1)^2$. This suggests the interpretation
$$(-1)^{x \cdot y}|x\rangle \langle y | =(-1)^{x_1y_1}|x_1\rangle \langle y_1|\otimes (-1)^{x_2y_2}|x_2\rangle \langle y_2|=(-1)^{x_1y_1+x_2y_2}| x_1 x_2 \rangle \langle y_1 y_2 |.$$ Thus $x \cdot y$ should be interpreted as an appropriate dot product of basis vectors.