Frustration Free Stoquastic Local Hamiltonian with Sub-Constant Gap is in $\NP$
Abstract
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{poly}(n)$. Aharonov and Grilo (2019) derandomized this algorithm and proved membership in NP for constant gap $\beta = \Omega(1)$. We present an improved algorithm and analysis, establishing membership in NP even when $\beta = \Omega(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)$.