  The local Hamiltonian problem plays the equivalent role of SAT in quantum
complexity theory. Understanding the complexity of the intermediate case in
which the constraints are quantum but all local terms in the Hamiltonian
commute, is of importance for conceptual, physical and computational complexity
reasons. Bravyi and Vyalyi showed in 2003, using a clever application of the
representation theory of C*-algebras, that if the terms in the Hamiltonian are
all two-local, the problem is in NP, and the entanglement in the ground states
is local. The general case remained open since then. In this paper we extend
the results of Bravyi and Vyalyi beyond the two-local case, to the case of
three-qubit interactions. We then extend our results even further, and show
that NP verification is possible for three-wise interaction between qutrits as
well, as long as the interaction graph is embedded on a planar lattice, or more
generally, "Nearly Euclidean" (NE). The proofs imply that in all such systems,
the entanglement in the ground states is local. These extensions imply an
intriguing sharp transition phenomenon in commuting Hamiltonian systems:
3-local NE systems based on qubits and qutrits cannot be used to construct
Topological order, as their entanglement is local, whereas for higher
dimensional qudits, or for interactions of at least 4 qudits, Topological Order
is already possible, via Kitaev's Toric Code construction. We thus conclude
that Kitaev's Toric Code construction is optimal for deriving topological order
based on commuting Hamiltonians.
