Stoquastic local Hamiltonian problem with small gap shown to be in NP
Frustration Free Stoquastic Local Hamiltonian with Sub-Constant Gap is in NP
Computational Complexity
Summary
This paper studies a physics-inspired math problem called the Stoquastic Local Hamiltonian problem, which involves quantum systems and energy states. The authors improve upon previous work by showing that deciding certain cases of this problem fits into the class NP, even when the energy gap is very small. This advances the understanding of how hard it is to solve these problems on classical computers under specific conditions. They also demonstrate why their method cannot extend beyond a certain limit.
What this means in practice
- •For quantum algorithm designers: Clarifies complexity boundaries for classical checking of quantum systems with small spectral gaps, guiding algorithm development.
- •For complexity theorists: Provides refined membership results for stoquastic local Hamiltonian problems, informing proofs about quantum-classical complexity relationships.
A theory result. No direct application yet.
Authors
Eshan Chattopadhyay, Oren Renard, Nicholas Spooner
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 $β$-gapped, frustration-free case, Bravyi, Bessen, and Terhal (2006) showed that the problem is MA-complete when $β= 1/\mathrm{poly}(n)$. Aharonov and Grilo (2019) derandomized this algorithm and proved membership in NP for constant gap $β= Ω(1)$. We present an improved algorithm and analysis, establishing membership in NP even when $β= Ω(1/(\log\log n))$. We complement our result with an explicit example demonstrating why the analysis does not extend directly to $β= o(1/\log\log n)$.