  The complexity of the commuting local Hamiltonians (CLH) problem still
remains a mystery after two decades of research of quantum Hamiltonian
complexity; it is only known to be contained in NP for few low parameters. Of
particular interest is the tightly related question of understanding whether
groundstates of CLHs can be generated by efficient quantum circuits. The two
problems touch upon conceptual, physical and computational questions, including
the centrality of non-commutation in quantum mechanics, quantum PCP and the
area law. It is natural to try to address first the more physical case of CLHs
embedded on a 2D lattice but this problem too remained open, apart from some
very specific cases. Here we consider a wide class of two dimensional CLH
instances; these are $k$-local CLHs, for any constant $k$; they are defined on
qubits set on the edges of any surface complex, where we require that this
surface complex is not too far from being "Euclidean". Each vertex and each
face can be associated with an arbitrary term (as long as the terms commute).
We show that this class is in NP, and moreover that the groundstates have an
efficient quantum circuit that prepares them. This result subsumes that of
Schuch [2011] which regarded the special case of $4$-local Hamiltonians on a
grid with qubits, and by that it removes the mysterious feature of Schuch's
proof which showed containment in NP without providing a quantum circuit for
the groundstate and considerably generalizes it. We believe this work and the
tools we develop make a significant step towards showing that 2D CLHs are in
NP.
