How to prove that the trace of n-qubit matrices satisfies ${\rm Tr}(XY)=2^n\sum_{M\in\{I,X,Y,Z\}^n} x_M y_M$?

Question

It is known that for n-qubit matrices X, Y $\in \mathbb{C}^{2^{n}\times 2^{n}}$ (and Pauli matrices $I, X, Y, Z$) such that $$ X = \sum_{M \in \{I, X, Y, Z\}^{n}} x_{M}M_{1}\otimes ... \otimes M_{n} $$ and $$ Y = \sum_{M \in \{I, X, Y, Z\}^{n}} y_{M}M_{1}\otimes ... \otimes M_{n} $$ their trace is $$ Tr(XY) = 2^{n} \sum_{M \in \{I, X, Y, Z\}^{n}}x_{M} y_{M} $$ and we can thus use the trace to calculate the coefficients $x_{M}, y_{M}$, but how do we know that is true? I understand that for all tensor products where $M \neq I$ the trace is zero but where exactly does the $2^{n}$ come from, and why is there still a summation in the trace if the tensor product only yields a non-zero trace for one scenario?

Answer 1

Letting $\sigma_j$ for $j \in \{I, X, Y, Z\}$ denote a Pauli matrix, its easy to verify the identity \begin{equation} \text{Tr}(\sigma_i \sigma_j) = 2 \delta_i^j \tag{1} \end{equation}

since $\sigma_i \sigma_j$ give the identity when $i=j$ but gives another non-identity Pauli operator (i.e. traceless) when $i \neq j$. Now its straightforward to show \begin{align} \text{Tr}(XY) &= \text{Tr}\left(\sum_{\mathbf{i}\in\{I,X,Y,Z\}^n} x_\mathbf{i} \sigma_{i_1} \otimes \cdots \otimes \sigma_{i_n} \sum_{\mathbf{j}\in\{I,X,Y,Z\}^n} y_\mathbf{j} \sigma_{j_1} \otimes \cdots \otimes \sigma_{j_n}\right)\tag{2} \\&= \sum_{\mathbf{i},\mathbf{j}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{j} \text{Tr}\left(\sigma_{i_1}\sigma_{j_1} \otimes \cdots \otimes \sigma_{i_n} \sigma_{j_n}\right)\tag{3} \\&= \sum_{\mathbf{i},\mathbf{j}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{j} \prod_{k=1}^n\text{Tr}\left(\sigma_{i_k}\sigma_{j_k}\right)\tag{4} \\&= \sum_{\mathbf{i},\mathbf{j}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{j} \left(2^n \prod_{k=1}^n \delta_{i_k}^{j_k} \right)\tag{5} \\&= 2^n \sum_{\mathbf{i},\mathbf{j}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{j} \delta_\mathbf{j}^\mathbf{i}\tag{6} \\&= 2^n \sum_{\mathbf{i}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{i} \tag{7} \end{align}

And so the $2^n$ comes from $\text{Tr}(\sigma_I)=2$ and the fact that every pair of terms between $X$ and $Y$ is either orthogonal or multiplies to $I_{2^n} := I \otimes \cdots \otimes I$ (with trace $2^n$). The sum remains because there are actually $4^n$ different pairs whose product is $I_{2^n}$. For example with three qubits, multiplying $x_{III} I_8$ with $y_{III} I_8$ results in an operator with nonzero trace, but so too does multiplying $x_{IXY} (I\otimes X \otimes Y)$ and $y_{IXY}(I\otimes X \otimes Y$), and so on.

Answer 2

where exactly does the $2^n$ come from

If you have a term in the product where all the Paulis are the same from both the $X$ and the $Y$, then you're left with the $2^n\times 2^n$ identity matrix. This has trace $2^n$.

why is there still a summation in the trace if the tensor product only yields a non-zero trace for one scenario?

When you multiply $X$ and $Y$, there are two summations (better to use different summation indices to make it super-clear!). The fact that the trace identifies equal terms accounts for one of the summations, leaving your answer with one summation.