# Confirming locality of a Hamiltonian through decomposition

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: $$$$H = \sum_i H_i$$$$

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

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.