In a belated revival of the Ghost Pontiff’s “Happy Paper Dance” ritual, I’d like to talk about the recent paper The k-local Pauli Commuting Hamiltonians Problem is in P by my student Jijiang (Johnny) Yan and his former advisor, Dave Bacon. The abstract is:
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.
This result follows a long string of papers that discuss the complexity of finding the ground state energy of k-local Hamiltonians, usually modified by various adjectives like “commuting” or “frustration-free” or “Pauli” or “in d dimensions.” Typically, these problems are shown to be somewhere between NP and QMA, and the subtle differences between these relate to issues such as topological order and the quantum PCP conjecture. In fact, one specific inspiration for this paper was 1102.0770, which showed that 3-qubit (or even 3-qutrit) commuting Hamiltonians could not have topologically-ordered ground states, while 4-qubit commuting Hamiltonians include the toric code, and 2-qubit non-commuting Hamiltonians include things that look like the toric code.
This paper shows that, in the case of commuting Pauli Hamiltonians, the difference between 3-local and 4-local is not important from a complexity point of view; indeed, it is possible to efficiently find the ground state of even 
At first this is shocking, but to see why it’s reasonable to expect this result, consider classical (commuting, Pauli) Hamiltonians. Determining whether these terms has a simultaneous ground state is equivalent to solving a linear system of equations over 
Please let me say that is a very interesting paper, and my appreciation and thanks are extended to Jijiang Yan (and to Dave and you too).
Regarding practical applications, it is natural to wonder whether an intractable 2-local but Hamiltonian whose individual terms are non-commuting might be mapped (by some ingenious means) onto an approximate k-local Hamiltonian whose individual terms are exactly commuting.
There are at least two well-known classes of computational methods that might be viewed as instances of this approximation strategy. The first are the well-known renormalization group methods; the second are the less-well-known (but still very important) symplectic integration methods; the key idea of the latter method is to find a numerical integration algorithm whose increments are exact for a Hamiltonian that is close to the desired Hamiltonian.
It is striking that both methods emerged from the community of accelerator physicists. And if you think about it, this is not surprising, because (like quantum computers) particle accelerators are iterated symplectomorphisms. Etienne Forest’s “Geometric integration for particle accelerators” (2006) provides a very lively introduction to this point of view.
So how large is this class of commuting-term Hamiltonians?
There’s also the Hastings apodization trick (see e.g. cond-mat/0508554) for making gapped Hamiltonians frustration-free, if not commuting.
However, for this paper, beware that it does NOT solve general commuting Hamiltonians. This class includes 3-SAT! Instead, it solves commuting PAULI Hamiltonians, and only determines whether all terms can simultaneously be in their ground states. If you take the special case of products of Z terms, then this is precisely a system of linear equations over F_2 in n variables.
Whoops … I had not entirely grasped (on first reading) the final point your post makes … still a fine analysis of an important class of problems.
Quantum Pontiff and Shtetl Optimized both have fallen silent … and so (by default) Wally’s vision for quantum computing — see yesterday’s Dilbert cartoon “How’s your quantum computer prototype coming along?” — is emerging as the dominant cultural narrative … is this really what we want? 🙁
There is one point which I would have appreciated having had expressed in the paper. The claim of the paper is actually that deciding wether a commuting Pauli Hamiltonian is frustration free or not is in P. However, the general problem of finding the ground state energy of a commuting Pauli Hamiltonian or deciding wether the GS energy of a commuting Pauli Hamiltonian is below some given energy is in my understanding an NP-hard problem. This could have also been stated somewhere in the paper. http://cs.stackexchange.com/questions/16691/min-2-xor-sat-and-max-2-xor-sat-are-they-np-hard
The reason I came to this is that I currently want to make a distinction between stabilizer Hamiltonians and commuting Pauli Hamiltonians and would like to motivate why such a distinction is meaningful.
I guess another way of explaining the paper would be that commuting Pauli Hamiltonians are essentially the same as XOR-SAT from a complexity point of view.