  Given a Hamiltonian that is a sum of commuting few-body terms, the commuting
Hamiltonian problem is to determine if there exists a quantum state that is the
simultaneous eigenstate of all of these terms that minimizes each term
individually. This problem is known to be in the complexity class quantum
Merlin-Arthur, but is widely thought to not be complete for this class. Here we
show that a limited form of this problem when the individual terms are all made
up of tensor products of Pauli matrices is efficiently solvable on a classical
computer and thus in the complexity class P. The problem can be thought of as
the classical XOR-SAT problem over a symplectic vector space. This class of
problems includes instance Hamiltonians whose ground states possess topological
entanglement, thus showing that such entanglement is not always a barrier for
the more general problem.
