Frustration Free Stoquastic Local Hamiltonian with Sub-Constant Gap is in NP

We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the QMA-complete Local Hamiltonian problem (Kitaev, Shen, and Vyalyi, 2002). For the $\beta$-gapped, frustration-free case, Bravyi, Bessen, and Terhal (2006) showed that the problem is MA-complete when $\beta =1\mathrm{/}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)$. Aharonov and Grilo (2019) derandomized this algorithm and proved membership in NP for constant gap $\beta =\mathrm{\Omega }(1)$. We present an improved algorithm and analysis, establishing membership in NP even when $\beta =\mathrm{\Omega }(1\mathrm{/}(\log \log n))$. We complement our result with an explicit example demonstrating why the analysis does not extend directly to $\beta =o(1\mathrm{/}\log \log n)$.