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


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.