We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the QMA-complete Local Hamiltonian problem. For the $\beta$-gapped, frustration-free case, Bravyi, Bessen and Terhal showed that the problem is MA-complete when $\beta= \frac{1}{\mathrm{poly}(n)}$. Aharonov And Grilo derandomized this algorithm, showing membership in NP for constant gap $\beta = \Omega(1)$.

We present an improved algorithm and analysis, establishing membership in NP even when $\beta = \Omega (\frac{1}{\log\log n})$.
We complement our result with an explicit example demonstrating why the analysis does not extend directly to $\beta = o(1/\log\log n)$.

Updated abstract.

We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the $\QMA$-complete Local Hamiltonian problem \cite{KSV02}. For the $\beta$-gapped, frustration-free case, \citet{BBT06} showed that the problem is $\MA$-complete when $\beta= \frac{1}{\poly(n)}$. \citet{AG19} derandomized this algorithm and proved membership in $\NP$ for constant gap $\beta = \Omega(1)$.

An improved algorithm and analysis of \cite{AG19} are presented, establishing membership in $\NP$ even when $\beta = \Omega (\frac{1}{\log\log n})$.
We complement our result with an explicit example demonstrating why the analysis does not extend directly to $\beta = o(1/\log\log n)$.