Source-linked AI summary
Frustration Free Stoquastic Local Hamiltonian with Sub-Constant Gap is in NP
Eshan Chattopadhyay, Oren Renard, Nicholas Spooner
TL;DR
For frustration-free stoquastic Local Hamiltonian, prior NP membership was known at constant soundness, leaving the subconstant regime open. This paper gives an improved analysis with NP membership at β = Ω(1/log log n), and an explicit example showing why the current approach does not directly extend below that threshold.
Problem
Prior work established NP membership for frustration-free stoquastic Local Hamiltonian at constant soundness, while the subconstant-soundness regime remained outside that result.
Source: §1 · p. 2, §1.2 · p. 5Method
The paper analyzes a random sequence of local terms and retains a short overlapping subsequence, using randomness in the analysis while keeping the NP algorithm deterministic.
Source: §1.1 · p. 3, §1.2 · p. 5Results
β = Ω(1/log log n) suffices for NP membership in the stated frustration-free projective uniform stoquastic problem.
Source: §1.1 · p. 3Takeaways & Limitations
The explicit example shows that local-frustration pruning cannot by itself extend the current algorithm below the 1/log log n threshold.
Source: §1.2 · p. 6The current progress measure cannot prune the search sufficiently for β = o(1/log log n), so extending the result requires a new approach.
Source: §1.1 · p. 3
Abstract
from arXiv · showhide
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)$.
1 Introduction
The paper studies frustration-free stoquastic local Hamiltonians, a sign-free restriction of the QMA-complete Local Hamiltonian problem, and improves the soundness threshold for NP membership beyond the constant-gap result. Its analysis uses overlapping lightcones and also identifies a boundary for the current approach.
1 Introduction
- The prior results establish MA-completeness at inverse-polynomial soundness and NP membership at constant soundness for the frustration-free projective uniform problem.The constant-soundness NP result is due to Aharonov and Grilo; the inverse-polynomial MA-completeness result is due to Bravyi, Bessen, and Terhal [BBT06] and extended to the uniform projective case by.Source: §1 · p. 2
1.1 Our results
- ProjUSLH with β = η/log log n is in NP for a constant η depending on k, d, and q.The result concerns the frustration-free projective uniform stoquastic problem.Source: §1.1 · p. 3
- A reduction from inverse-polynomial-soundness instances to the stated 1/log log n regime would imply MA = NP.The corollary specifies a reduction from ProjUSLH with q=2 and k=6.Source: §1.1 · p. 3
- The analysis does not directly extend below β = o(1/log log n): exponentially many sequentially frustrated candidates can appear equally promising to the progress measure.The authors say extending the theorem would require a new approach.Source: §1.1 · p. 3, §1.2 · p. 6
1.2 Technical Overview
- Restricting enumeration to lightcones rather than whole graph balls improves the earlier constant-soundness NP algorithm to ε ≥ 1/√(log log n).The bound follows from enumerating overlapping candidates in polynomial time.Source: §1.2 · p. 4
- The alternative analysis uses a random sequence only in the proof, retaining a short overlapping subsequence while the NP algorithm remains deterministic.This avoids the square-root loss from the O(1/ε²)-layer argument.Source: §1.1 · p. 3, §1.2 · pp. 5–6
1.3 Discussions
- With D-dimensional lattice geometry, the techniques yield an algorithm for soundness as small as β = 1/(log n)^O(1/D).The paper notes that general lattice Local Hamiltonian ground energies also admit deterministic polynomial-time approximation at inverse-polylogarithmic additive accuracy.Source: §1.3 · p. 7
- The results remain restricted to uniformity-preserving reductions; extending frustration-expansion analysis to non-uniform weights is challenging because frustration may depend on global Hamiltonian properties.Source: §1.3 · p. 7
2 Preliminaries
The preliminaries define uniform stoquastic projectors and the promise-problem setting, then use a graph on strings to frame the analysis of YES and NO instances.
2.1 Definitions
- A uniform stoquastic projector is entrywise non-negative, acts nontrivially on at most k qudits, and is a sum of orthogonal uniform subset-state projectors.The problem restricts each qudit to participation in at most d = O(1) terms.Source: §2.1 · pp. 7–8
2.2 The Associated Graph and Its Analysis
- The associated graph has strings in Σ^n as vertices, with an edge when some instance projector has a positive matrix element between the two strings.A string is BAD when it is annihilated on the diagonal by at least one projector.Source: §2.2 · p. 8
- In a YES instance, every graph component containing a ground-state support string contains no BAD strings, by Lemma 2.1 [BBT06, Appendix A.2.1].The lemma applies for arbitrary ε > 0.Source: §2.2 · p. 8
- For NO instances, the frustration-versus-expansion lemma of Aharonov and Grilo is used to find BAD strings.The section focuses on instances with perfect completeness or non-trivial soundness ε > 0.Source: §2.2 · p. 8
3 Our Algorithm
The verifier searches for BAD strings through overlapping sequences of local terms. A random-process argument proves that short such sequences suffice for the stated inverse-log-log gap, yielding NP membership.
3 Our Algorithm
- ProjUSLHq(k, d, 0, η / log log n) is in NP for a constant η = η(k, d, q).The polynomial-time bound assumes k, d, and q are constants.Source: §3 · pp. 9–10
- The verifier enumerates overlapping sequences and their reachable strings, rejecting when it finds a BAD string; YES instances are accepted because all strings reached from a valid witness are GOOD.For NO instances, the structural lemma guarantees a sequence that reaches a BAD string.Source: §3 · p. 9
- The verifier's enumeration is polynomial when k, d, and q are constant and ε is at least η / log log n.The count of next terms in an overlapping sequence is bounded by kdr after r terms have been retained.Source: §3 · pp. 9–10
3.1 Setup
- The setup tracks the support reached from a witness under sampled terms; if no BAD string appears, sufficient expected frustration forces support growth beyond the string space.The argument relates expected final support size to frustration at each intermediate step.Source: §3.1 · pp. 11–12
3.2 Uniformly Random Sequence
- Uniformly random term sequences force a BAD string to appear, but do not bound the maximal path length from the starting string to it.The support-size contradiction follows for T ≥ 8n.Source: §3.2 · p. 12
3.3 The Chopped Sequence
- The chopped process removes terms with long overlapping subsequences while retaining expected frustration of at least ε/2, so support expansion still forces a BAD string.The construction bounds the maximal distance to a BAD string by ℓε.Source: §3.3 · pp. 13–14
- For every starting string, a term and a rooted overlapping sequence of length less than ℓε lead to a BAD string.The sequence's support contains a string BAD for its root term.Source: §3.3 · p. 14
4 An Instance For Which Exponentially Many Overlapping Sequences Are δ-valid
The section constructs a frustrated tree instance with many rooted overlapping sequences that are sequentially δ-frustrated for a shared witness, illustrating the limitation of the analysis's progress measure.
4 An Instance For Which Exponentially Many Overlapping Sequences Are δ-valid
- For every δ > 0, the paper gives an explicit O(δ)-frustrated instance with a large subset of rooted overlapping sequences sequentially δ-frustrated for one witness.The phenomenon means restricting enumeration to that subset does not improve the worst-case sequence-length dependence.Source: §4 · p. 15
4.1 Construction
- The construction places one qudit at each node of a complete depth-T k-ary tree and associates a term with each node.Each term's block comprises a parent register and its child registers; shared registers receive different parent and child actions.Source: §4.1 · p. 15, Figure 1 · p. 16
4.2 Validity of the Instance
- The instance belongs to ProjUSLHq(k + 1, d = 2), since terms are at most (k + 1)-local and each non-root qudit participates in at most two terms.Its projectors use singleton uniform subset states.Source: §4.2 · p. 15
- The constructed instance is δ/8k-frustrated.The proof bounds the energy for an arbitrary state.Source: §4.2 · p. 16
- For every internal node u ∈ V, Lemma 4.3 defines an operator M(u), whose maximum eigenvalue satisfies λmax(M(u)) ≤ 2 − δ/2.Source: §4.2 · p. 17
4.3 Doubly Exponentially Many Sequentially Frustrated Sequences
- Nice overlapping sequences correspond to ordered top-down subtrees, and the construction yields many such sequences of length at most ℓε.The count is derived by considering subsets of leaves in a complete subtree.Source: §4.3 · pp. 17–18
- Reversing any nice overlapping sequence gives a sequence sequentially δ-frustrated for the shared witness x = 0^n.The proof concludes that every term application in the reversed sequence is sequentially δ-frustrated.Source: §4.3 · p. 18