How to express $n$-qubit Hermitian operator with Pauli matrices

Question

How can we prove that all $n$-qubit Hermitian matrices can be written in terms of Pauli matrices $I$, $X$, $Y$, and $Z$ as $$ \sum_{W_k \in \{I, X, Y, Z\}} a_{W_1,\dots,W_n}W_{1}\otimes ... \otimes W_{n} $$ where $a_{W_1,\dots,W_n} \in \mathbb{R}$?

Answer 1

A simple approach is to overdo it a little and show that $n$-qubit Pauli operators form an orthogonal basis in the real vector space $L_H(\mathbb{C}^{2^n})$ of $n$-qubit Hermitian operators with appropriately defined inner product. To that end, we first show that $\langle A,B\rangle_{HS}:=\mathrm{tr}(A^\dagger B)$ is an inner product$^1$. Next, we calculate that for any two Pauli operators $W=W_1\otimes\dots\otimes W_n$ and $W'=W'_1\otimes\dots\otimes W'_n$ we have $\langle W,W'\rangle_{HS}=0$ if and only if $W\ne W'$. This implies$^2$ linear independence. Finally, there is a linear bijection between $L_H(\mathbb{C}^k)$ and $\mathbb{R}^{k^2}$, so $\dim L_H(\mathbb{C}^k)=k^2$. But there are $4^n$ Pauli operators in $L_H(\mathbb{C}^{2^n})$, so they form a basis.

---

^{$^1$ The function $\langle .,.\rangle_{HS}$ is known as the Hilbert-Schmidt inner product.
$^2$ Because the coefficient in front of $W_k$ in a linear combination $A$ is proportional to $\langle W_k,A\rangle_{HS}$.}