Exercise 2.33 in Nielsen & Chuang QCQI book - H tensor n

Question

The question on the book is:

The Hadamard operator on one qubit may be written as $$\frac{1}{\sqrt{2}}[(|0\rangle + |1\rangle)\langle0| + (|0\rangle - |1\rangle)\langle1|]$$ Show explicitly that the Hadamard transform on $n$ qubits, $H^{\otimes n}$, may be written as $$H^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum_{x,y}(-1)^{x\cdot y}|x\rangle\langle y|.\quad\quad \textrm{(2.55)}$$ Write out an explicit matrix representation for $H^{\otimes 2}$.

$H^{\otimes 2}$ is easy. It is $\frac{1}{2}\begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{bmatrix} $. It can be obtained as the Kronecker product of two $\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1\\ 1 & -1\\ \end{bmatrix}$. However, I am not sure how this is linked to (2.55). Say $|11\rangle\langle11|$. This term should has a coefficient of 1 according to the matrix of $H^{\otimes 2}$. (I think it is the bottom right corner.) However, according to (2.55), the coefficient seems to be -1 since $x=y=3$ and $x\cdot y=9$. In my understanding, the ranges for both $x$ and $y$ are $\{0, 1, 2, 3\}$.

Am I wrong with something? Do I understand the meanings of $x$, $y$, and $\cdot$ correctly? Or, is (2.55) wrong?

Answer 1

Welcome to quantum computing's stackexchange!

Your tensor product is correct, the issue is with your understanding of $x\cdot y$. The value is calculated through an element-wise dot product rather than converting it into a decimal and then multiplying. Which means that $$ 11 \cdot 11 = [(1 \cdot 1) + (1\cdot 1)] \text{ mod } 2 = 0 $$ Sidenote: You can further understand this notation by thinking of what the power of $-1$ signifies, if you notice that the single Hadamard gate can also be written in the same way as you have written, try expanding the tensor product of two qubit Hadamard using the $x$ and $y$ notation to see why it's element-wise dot product

Answer 2

Be careful : in expression (2.55), the term $x \cdot y$ is in fact the sum (modulo 2) of the bitwise products : $$x \cdot y=x_{0} y_{0} \oplus x_{1} y_{1} \oplus \cdots \oplus x_{n-1} y_{n-1}$$

so, for $x = y = 3$, you have $x \cdot y = 1*1 \oplus 1*1 = 0$