ArXiv · 2026
Stoquasticity, originating in sign-problem-free physical systems, gives rise to sf StoqMA, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between sf MA and sf AM. Unentanglement similarly gives rise to sf QMA(2), introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes sf QMA to two unentangled proofs and still has only the trivial sf NEXP upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via sf StoqMA(2), the class of unentangled stoquastic Merlin–Arthur proof systems. Beyond its complexity-theoretic interest, sf StoqMA(2) is connected to the optimality of non-negative tensor optimization algorithms. We highlight: 1. sf NP ⊆ sf StoqMA(2) with widetildeO(√n)-qubit proofs and completenes 1-2^(-rm polylog(n)). Conversely, the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) gives an exponential-time upper bound for sf StoqMA(2). Our tightened analysis shows the optimality of our protocol and the BKS algorithm under ETH. 2. For sf StoqMA(2)₁, the parameter dependence in the general ETH-optimal time bound can be exponentially improved, or the bound achieved simultaneously with polynomial space. 3. For logarithmic-size proofs, sf NP ⊆ sf StoqMA(2)_log with completeness 1-O(n⁻²) and vanishing gap, while sf StoqMA(2)_log ⊆ sf MA. Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption sf MA=sf NP. Our lower bounds are obtained by stoquastizing the short-proof sf QMA(2) protocols using distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework.
Try inveni