Skip to content

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

Sep 2026 · Electron. Colloquium Comput. Complex. · Vol abs/2609.38910 · 0 citations · 23 references
Computer Science

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

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.