The Exercise

Take $n$ qubits and a Hamiltonian $H = \sum_{k=1}^{L} H_k$ on them in which each term $H_k$ acts on at most $c$ of the qubits, with $c$ fixed while $n$ grows. For $c = 2$ the terms are fields on single qubits and couplings between pairs of qubits. The exercise asks to show that this restriction bounds the number $L$ of terms by a polynomial in $n$.

The library states the claim for a Hamiltonian expanded in the Pauli strings defined below, tensor products of the Pauli matrices with one factor on each qubit, with real coefficients.

A Quantum System

A quantum system $S$ is described by its state space, a finite dimensional complex Hilbert space.^✦ The qudit with $d$ levels is the system with state space $\mathbb{C}^d$ with its standard inner product; a qubit is the qudit with two levels, and the qudit with $2^n$ levels is a register of $n$ qubits.^✦ An observable $A$ on $S$ is a self adjoint operator on the state space of $S$, $A^\dagger = A$.^✦

Pauli Strings

The Pauli matrices are the four complex $2 \times 2$ matrices $$\sigma_0 = I, \qquad \sigma_1 = X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad \sigma_2 = Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \qquad \sigma_3 = Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}.$$(1)^✦

For a string $g = (g_1, \dots, g_n)$ of indices in $\{0, 1, 2, 3\}$, one for each of $n$ qubits, the Pauli string $\sigma_g$ is the operator on the $n$ qubits $$\sigma_g = \sigma_{g_1} \otimes \cdots \otimes \sigma_{g_n}, \qquad (\sigma_g)_{ij} = \prod_{k=1}^{n} (\sigma_{g_k})_{i_k j_k},$$(2)^✦ with rows and columns labelled by strings of bits $i = (i_1, \dots, i_n)$ and $j = (j_1, \dots, j_n)$. As a $2^n \times 2^n$ matrix, its rows and columns are labelled $0, \dots, 2^n - 1$ by reading each string of bits as a binary number.^✦

The support of $g$ is the set of qubits at which the factor $\sigma_{g_k}$ is not the identity, $$\operatorname{supp} g = \{\, k : g_k \neq 0 \,\},$$(3)^✦ and its size $|\operatorname{supp} g|$ is the number of qubits on which $\sigma_g$ acts.

For a string $g$ and a real number $h$, the Pauli string Hamiltonian $h\,\sigma_g$ is the observable on the register of $n$ qubits that acts on $\mathbb{C}^{2^n}$ as $h$ times the Pauli string $\sigma_g$ on $2^n$ levels.^✦

The Claim

The terms $h_g \sigma_g$ with $|\operatorname{supp} g| \le c$ stand for the terms $H_k$ of the exercise, so their number $L$ is at most the size of $T$.

What Is Checked

The claim (4) is stated over the Pauli string Hamiltonians $h_g \sigma_g$, observables on the register of $n$ qubits built from the Pauli strings (2), and over the support (3), which expresses the locality condition.

The library proves that every Pauli string on $2^n$ levels is Hermitian.