Is there any known characterization of k-Local Hamiltonian (k-LH) to distinguish if it has an efficient guiding state?

Question

In general, k-LH promise problem, where input is given as $<H, a, b>$, is QMA complete if $a-b>1/{\textrm{poly}(n)}$.

Also, if a guiding state (say, a "good" approximation to the ground state) for the Hamiltonian $H$ is provided, then there exists a BQP algorithm for the problem. Thus, assuming $BQP\neq QMA$ implies finding such a guiding state must be hard for some Hamiltonians.

There exist some heuristics that can be used to find such guiding states, such as the' Hartree-Fock method' (HFM). HFM is known to fail in finding the guiding state for some Hamiltonians.

My question: Is there a known characterization of the local Hamiltonians that guarantees it will have a good guiding state?

Answer 1

^{CW, might be off-base; just some thoughts for now}

---

I think the first question is likely very hard to answer. If you are looking for a way to easily know whether a particular, polynomially described subclass of kLH has an easily constructable ansatz that overlaps sufficiently with the true ground state and hence is necessarily in BQP, this seems similar to asking whether a particular, polynomially described subclass of 3SAT is also necessarily a subclass of P. But I think there are theorems that state that such a problem of "is in P" may, itself, be NP-complete - perhaps some consequence of Rice's theorem.

Thus I think there's a similar theorem, or I'll conjecture, that it's at least NP-hard to have a classical algorithm that, when given a (polynomially bounded) description of some subclass of kLH along with some (polynomially bounded) descriptions of circuits to prepare the ansatz, and to determine whether said subclass is in BQP.

The boundary between complexity classes is always pretty fuzzy. We have great (classical) results stemming from the PCP theorem and hardness-of-approximation results; the guided local Hamiltonian problem likewise gives a sliding scale between P, BQP, and QMA, but I'm not sure if we can have an efficient procedure to know what other problems have such an overlap.