Confirming locality of a Hamiltonian through decomposition

Question

I was trying to understand Trotterization. The given Hamiltonian is decomposed into a sum of $k$-local Hamiltonians which can be exponentiated in $O(1)$ gate complexity. After which the Trotter approximation is applied. The Hamiltonian can be represented as: $$ \begin{equation} H = \sum_i H_i \end{equation} $$

Where $H_i$ is a $k$-local Hamiltonian. I wanted to see how can I achieve the above decomposition. I came to know that decomposition into the Pauli basis is trivially possible(ref). The decomposition can be written as:

$$ H = \sum_{\gamma_1\dots\gamma_n=0}^4 c_{\gamma_1\dots\gamma_n} \sigma_{\gamma_1\dots\gamma_n} $$

Now a follow-up I had was regarding on the locality of the decomposition. Suppose that in the Pauli decomposition of $H$ acting on $n$ qubits,

$$ \exists \sigma_{\gamma_1\dots\gamma_n} \text{ s.t } c_{\gamma_1\dots\gamma_n} \geq 0 \\ |\{i|\gamma_i \geq 0\}| \geq k $$

Simply put, there exists a term in the sum such that it has atleast $k$ positions on which the operation is not $\sigma_0$ or $I$.

So can I trivially say that the Hamiltonian given is not $k$-local?

My claim is that it is not a $k$-local Hamiltonian if the above criteria satisfies. I have an approach but I just wanted to verify if this is the correct approach.

Since Pauli matrices along with $I$ form a basis of size $4^n$, a linear combination of even $4^n - 1$ terms can't be used to express the term that is not accounted for. This implies that if there exists a term that acts on more than $k$ qubits non-trivially, then it can't be broken down into operations of less than $k$ qubits.

But what I'm worried about is what about a change of basis, or something of that sort. If someone can guide me towards a more concrete proof, or support it by dismissing the doubts I have it would be great :D

Answer 1

As long as you tweak your condition to require strict inequalities, $$ \exists \sigma_{\gamma_1\dots\gamma_n} \text{ s.t } c_{\gamma_1\dots\gamma_n} > 0 \tag{1} \\ |\{i|\gamma_i > 0\}| > k $$ then yes, the Hamiltonian is not $k$-local by definition. An operator being $k$-local by definition means that it acts nontrivially on only $k$ subsystems, i.e. $\forall \boldsymbol{\gamma} \, s.t. \, c_\boldsymbol{\gamma} > 0$, it holds that $|\{i|\gamma_i > 0\}| \leq k$. The condition (1) is the logical negation of the definition of $k$-local, and is therefore the definition of a not-$k$-local operator.

Your argument about not being able to reconstruct a $(k+1)$-local term from any combination of $k$-local terms is true and follows from the fact that the Pauli operators are orthonormal, $\text{Tr}(\sigma_{\boldsymbol{\gamma}} \sigma_{\boldsymbol{\lambda}}) = \delta_\boldsymbol{\gamma}^\boldsymbol{\lambda}I_{2^n}$, but this also means that any $k$-local Pauli operator cannot be written as linear combinations of other $k$-local Pauli operators and so its not a relevant fact.

It is indeed worth considering changes of basis affecting locality since this definition of locality is not preserved under change of basis - this is exploited when compiling a $\exp(i \theta ZZZ)$ gate into $CNOT$s and $\exp(i \phi Z)$ gates, for example. In that case, you can implement a unitary generated by a $k$-local Hamiltonian using only $1$- and $2$-local unitaries, but clearly the final operation still acts nontrivially on $k$ subsystems.