pipette
ESEspañol

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

Eshan Chattopadhyay, Oren Renard, Nicholas Spooner

Preprint

In the authors' words

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 . Aharonov and Grilo (2019) derandomized this algorithm and proved membership in NP for constant gap . We present an improved algorithm and analysis, establishing membership in NP even when . We complement our result with an explicit example demonstrating why the analysis does not extend directly to .

Main resultLimitation the authors admit

Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.