Suppose we have a $k$-local Hamiltonian with each of $m$ terms acting on $k$ of $n$ qudits of constant dimension $d$:


If at least some of the terms don't commute, e.g., if $[H_i,H_j]\ne 0$ for some $i,j$, then we can use our favorite Hamiltonian simulation algorithm to estimate the energy of any eigenstate $|\psi\rangle$ of $H$; generally the Baker-Campbell-Hausdorff formula can help control the error on the non-commutative components. Nonetheless, learning the specific ground state and its energy is the canonical QMA-complete problem; even a quantum computer can't help in such a case.

But, if all the terms of the Hamiltonian commute, e.g., if for all $i,j\le m$ we have $[H_i,H_j]=0$, then is it much easier to learn the ground state, or at least the energy of the ground state?

Is such a problem in BQP? Or even in NP? We are only steering our car forward with such a Hamiltonian; we don't do any parallel parking.

  • 1
    $\begingroup$ Sorry about the deleted question -- just to be clear, I am happy to answer any meaningful question along those lines, there's certainly a bunch of interesting (but probably also very hard) questions one can ask in that regard. But without specifying what basis transformations you mean, it is a bit like the deleted answer on this questions. $\endgroup$ Commented Dec 27, 2023 at 15:11
  • $\begingroup$ ... having said that, I think it is important to edit it, to make more clear what you ask, and why. (E.g., why would you think that the fact whether two operators commute depends on the basis, or that a local basis transformation chances locality (in the CS sense), etc.?) $\endgroup$ Commented Dec 27, 2023 at 15:41
  • $\begingroup$ Thanks for the feedback. I had seen a really good presentation from Irani touching briefly on the Kagame lattice - which is highly frustrated - and she hinted that studies with classical algorithms such as DMRG suggested that the ground state was highly entangled. But if being frustration-free is basis-dependent and being highly entangled is basis-independent then that relationship frustration-freeness and entangled ground states is illusory maybe? $\endgroup$ Commented Dec 27, 2023 at 15:52
  • $\begingroup$ First, be careful with "frustrated" vs. "frustration-free" -- these typically mean two different things. If it is the kagome, then it should be about (geometric) frustration. This is also a basis-independent concept, at least more-or-less -- I'm not sure there is a 100% formal definition of frustrated (or rather, there are many, which are probably contradictory -- you know it when you see it). But just as for "stoquastic" ("sign-problem free"), a good definition should include the notion that this is up to a suitable basis choice. $\endgroup$ Commented Dec 27, 2023 at 16:37
  • $\begingroup$ P.S.: Maybe we should migrate the discussion to the other question ... $\endgroup$ Commented Dec 27, 2023 at 16:37

1 Answer 1


Much less is known about the complexity of commuting local Hamiltonians than one might think or hope.

The best we know in the general case is that it is (1) NP-hard (as already classical local Hamiltonians are NP hard), and (2) contained in QMA (as any local Hamiltonian problem is contained in QMA).

Beyond that, we only have proofs of the NP-containment for certain classes of Hamiltonians, mostly on planar or almost-planar graphs. The (afaik) most recent paper on the topic, which should have references to relevant prior work, is https://arxiv.org/abs/2309.04910.

(To give a quick intuition why containment in NP is not easy: The fact that a Hamiltonian has commuting terms does not mean that the ground state is trivial; e.g., all topological fixed-point models such as the Toric Code fall into that class, and they have highly non-trivial ground states. Thus, it is not generally clear that commuting Hamiltonians have ground states which can be supplied in a more easily checkable way than as quantum states, i.e. QMA proofs.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.