The power of unentanglement without destructive interference

Stoquasticity, originating in sign-problem-free physical systems, gives rise to $\mathsf{S}\mathsf{t}\mathsf{o}\mathsf{q}\mathsf{M}\mathsf{A}$, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between $\mathsf{M}\mathsf{A}$ and $\mathsf{A}\mathsf{M}$. Unentanglement similarly gives rise to $\mathsf{Q}\mathsf{M}\mathsf{A}(2)$, introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes $\mathsf{Q}\mathsf{M}\mathsf{A}$ to two unentangled proofs and still has only the trivial $\mathsf{N}\mathsf{E}\mathsf{X}\mathsf{P}$ upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via $\mathsf{S}\mathsf{t}\mathsf{o}\mathsf{q}\mathsf{M}\mathsf{A}(2)$, the class of unentangled stoquastic Merlin–Arthur proof systems. Beyond its complexity-theoretic interest, $\mathsf{S}\mathsf{t}\mathsf{o}\mathsf{q}\mathsf{M}\mathsf{A}(2)$ is connected to the optimality of non-negative tensor optimization algorithms. We highlight: 1. $\mathsf{N}\mathsf{P}\subseteq \mathsf{S}\mathsf{t}\mathsf{o}\mathsf{q}\mathsf{M}\mathsf{A}(2)$ with $\tilde{O}(\sqrt{n})$-qubit proofs and completenes $1-2^{-\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(n)}$. Conversely, the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) gives an exponential-time upper bound for $\mathsf{S}\mathsf{t}\mathsf{o}\mathsf{q}\mathsf{M}\mathsf{A}(2)$. Our tightened analysis shows the optimality of our protocol and the BKS algorithm under ETH. 2. For $\mathsf{S}\mathsf{t}\mathsf{o}\mathsf{q}\mathsf{M}\mathsf{A}(2{)}_1$, 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, $\mathsf{N}\mathsf{P}\subseteq \mathsf{S}\mathsf{t}\mathsf{o}\mathsf{q}\mathsf{M}\mathsf{A}(2{)}_{\log }$ with completeness $1-O(n^{-2})$ and vanishing gap, while $\mathsf{S}\mathsf{t}\mathsf{o}\mathsf{q}\mathsf{M}\mathsf{A}(2{)}_{\log }\subseteq \mathsf{M}\mathsf{A}$. Consequently, quantum-inspired randomness enables \emph{exponentially} shorter unentangled proofs even under the assumption $\mathsf{M}\mathsf{A}=\mathsf{N}\mathsf{P}$. Our lower bounds are obtained by stoquastizing the short-proof $\mathsf{Q}\mathsf{M}\mathsf{A}(2)$ protocols using distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework.