The power of unentanglement without destructive interference

Abstract

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

arXiv comment85 pages, 2 figures, 7 protocols, and 2 algorithms. Abstract shortened due to the arXiv length restriction. v3: Minor changes, to appear in SODA 2027. v2: Added the results that StoqMA(k)_log is in MA and StoqMA_log = BPP, and made minor changes