The Exercise

The Hadamard gate acts on one qubit as the matrix $$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$(1) in the computational basis $|0\rangle, |1\rangle$; its entries are written $H_{ab}$, for bits $a$ and $b$. Applied to each of $n$ qubits at once it gives the Hadamard transform $H^{\otimes n}$. The exercise asks for its matrix elements $\langle x | H^{\otimes n} | y \rangle$ between computational basis states, labelled by strings $x$ and $y$ of $n$ bits, in closed form for every $n$, and for the matrix of $H^{\otimes 2}$ written out in full.

The Hadamard Transform

The Hadamard transform $H^{\otimes n}$ on $n$ qubits is the real matrix with rows and columns labelled by the strings $x = x_1 x_2 \dots x_n$ of $n$ bits, defined by recursion on $n$: $$H^{\otimes 0} = 1, \qquad H^{\otimes (n+1)}_{xy} = H_{x_1 y_1} \, H^{\otimes n}_{x' y'},$$(2)^✦ where $x'$ and $y'$ are $x$ and $y$ with their first bits removed. On no qubits there is a single string, the empty one. The recursion is the tensor product $H^{\otimes (n+1)} = H \otimes H^{\otimes n}$ written entry by entry, with the first qubit split off. The entry in row $x$ and column $y$ is the matrix element $H^{\otimes n}_{xy} = \langle x | H^{\otimes n} | y \rangle$.

The basis order $b$ for two qubits is the list of the four strings of two bits in the order of the computational basis $|00\rangle, |01\rangle, |10\rangle, |11\rangle$: $$b_0 = 00, \qquad b_1 = 01, \qquad b_2 = 10, \qquad b_3 = 11.$$(3)^✦ In this order $H^{\otimes 2}$ is the $4 \times 4$ matrix whose entry in row $j$ and column $k$ is $H^{\otimes 2}_{b_j b_k}$.

The Claim

For strings $x$ and $y$ of $n$ bits, $x \cdot y = x_1 y_1 + \dots + x_n y_n$ counts the places where both carry a $1$, and $(-1)^{x \cdot y}$ is $-1$ exactly when that count is odd.

What Is Checked

The claim is stated over the Hadamard transform $H^{\otimes n}$ built from the gate (1) by the recursion (2), and, on two qubits, over the basis order (3). The library proves that every matrix element of $H^{\otimes n}$, for every number of qubits, has the closed form (4), and that the transform on two qubits, read in that order, is the matrix (5).