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)$.