analiza aiqbench
This is theoretical quantum complexity work, not a hardware or application result. It defines StoqMA(2), a class of unentangled, sign-problem-free quantum proof systems, and proves containments and lower bounds relating it to NP, MA, and known algorithms under standard conjectures like ETH. For readers, the main value is in clarifying which computational advantages quantum-inspired structure can and cannot provide, and the link to non-negative tensor optimization gives it some relevance beyond pure theory.
The power of unentanglement without destructive interference
arXiv:2604.27886v3 Announce Type: replace Abstract: 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} \subseteq {\sf StoqMA}(2)$ with $\widetilde{O}(\sqrt{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 logarithmic-size proofs, ${\sf NP} \subseteq {\sf StoqMA}(2)_{\log}$ with completeness $1-O(n^{-2})$ and vanishing gap, while ${\sf StoqMA}(2)_{\log} \subseteq {\sf MA}$. Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption ${\sf MA}={\sf NP}$. 3. For ${\sf 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 ${\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.
Abstract: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} \subseteq {\sf StoqMA}(2)$ with $\widetilde{O}(\sqrt{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 logarithmic-size proofs, ${\sf NP} \subseteq {\sf StoqMA}(2)_{\log}$ with completeness $1-O(n^{-2})$ and vanishing gap, while ${\sf StoqMA}(2)_{\log} \subseteq {\sf MA}$. Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption ${\sf MA}={\sf NP}$. 3. For ${\sf 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 ${\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.
85 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
Quantum Physics (quant-ph); Computational Complexity (cs.CC)
arXiv:2604.27886 [quant-ph]
(or arXiv:2604.27886v3 [quant-ph] for this version)
Text integral sub licența deschisă a publicației · 303 cuvinte
Subiecte conexe
Game Design Creativity evals
LessWrong · 12 oct. 2026
Problems of Proliferation
LessWrong · 29 sept. 2026
The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
arXiv · 1 oct. 2026
Predicting and Repairing Merge Collapse in Large Language Models
arXiv · 5 oct. 2026