Notation in formula for tensor product of Hadamard matrix

Question

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?

Answer 1

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.