pipette
ENEnglish

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

Eshan Chattopadhyay, Oren Renard, Nicholas Spooner

Preprint

En palabras de los autores

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 .

Resultado principalLimitación que admiten los autores

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.