  We study the complexity of local Hamiltonians in which the terms pairwise
commute. Commuting local Hamiltonians (CLHs) provide a way to study the role of
non-commutativity in the complexity of quantum systems and touch on many
fundamental aspects of quantum computing and many-body systems, such as the
quantum PCP conjecture and the area law. Despite intense research activity
since Bravyi and Vyalyi introduced the CLH problem two decades ago [BV03], its
complexity remains largely unresolved; it is only known to lie in NP for a few
special cases. Much of the recent research has focused on the physically
motivated 2D case, where particles are located on vertices of a 2D grid and
each term acts non-trivially only on the particles on a single square (or
plaquette) in the lattice. In particular, Schuch [Sch11] showed that the CLH
problem on 2D with qubits is in NP. Aharonov, Kenneth and Vigdorovich~[AKV18]
then gave a constructive version of this result, showing an explicit algorithm
to construct a ground state. Resolving the complexity of the 2D CLH problem
with higher dimensional particles has been elusive. We prove two results for
the CLH problem in 2D:
  (1) We give a non-constructive proof that the CLH problem in 2D with qutrits
is in NP. As far as we know, this is the first result for the commuting local
Hamiltonian problem on 2D beyond qubits. Our key lemma works for general qudits
and might give new insights for tackling the general case.
  (2) We consider the factorized case, also studied in [BV03], where each term
is a tensor product of single-particle Hermitian operators. We show that a
factorized CLH in 2D, even on particles of arbitrary finite dimension, is
equivalent to a direct sum of qubit stabilizer Hamiltonians. This implies that
the factorized 2D CLH problem is in NP. This class of CLHs contains the Toric
code as an example.
