If all terms of a local Hamiltonian commute, how hard is it to learn the ground state (energy)?

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

$$H=H_1+H_2+\cdots+H_m.$$

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.

• 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. Commented Dec 27, 2023 at 15:11
• ... 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.?) Commented Dec 27, 2023 at 15:41
• 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? Commented Dec 27, 2023 at 15:52
• 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. Commented Dec 27, 2023 at 16:37
• P.S.: Maybe we should migrate the discussion to the other question ... Commented Dec 27, 2023 at 16:37