Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.27886

The power of unentanglement without destructive interference

Yupan Liu, Pei Wu

quant-phcs.CCSubmitted Apr 30, 2026• Announced May 1, 2026• 4 citations• Revised Oct 13, 2026 (v3)
v1 · Apr 30, 2026v2 · Jul 12, 2026v3 · Oct 13, 2026
arXivHTMLPDF

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.

Comments
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

Related papers

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems

William Gay, Fernando Granha Jeronimo

Interference and entanglement are among the most fundamental properties of quantum mechanics. In this work, we investigate the power of interference in the role of detecting entanglement in the context of quantum Merlin-Arthur verification. In particular, we show that unentanglement gives no additional power to stoquastic Merlin-Arthur proof systems, whose restriction to a classical gate set results in entrywise non-negative acceptance operators and non-negative optimal witnesses, therein removing destructive interference from the verification process. Our results show that for any polynomial number of unentangled witnesses $k = k(n)$, \[ \mathsf{StoqMA}(k) = \mathsf{StoqMA}. \] The analytic core of this result is a new non-negative de Finetti theorem for separately bosonic states. If a mixed state $ρ$ is supported on the tensor product of symmetric subspaces of $\mathcal{H}_1^{\otimes R} \otimes \mathcal{H}_2^{\otimes R} \otimes \cdots \otimes \mathcal{H}_k^{\otimes R}$ then there exists a separable state $τ$ on $\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k$ such that \[ \mathrm{Tr}\big(M(ρ_{\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k} - τ)\big) \le 2 \sqrt{\frac{k\, \log_2\dim(\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k)}{R-1}}, \] simultaneously for all non-negative effects $M$. For any such operator $M$, one can define the separately symmetric lift $\mathrm{SS}_R(M)$ whose largest eigenvalue approximates the maximum acceptance probability of $M$ over product states within the same error bound. Such a lift can be approximated by a stoquastic verifier, giving that product-state constraint of $\mathsf{StoqMA}(k)$ verifiers can be absorbed into a polynomially larger one-witness $\mathsf{StoqMA}$ verification, while preserving an inverse polynomial completeness-soundness gap.

quant-pharXiv:2605.16249•May 18, 2026•2 citations

The Power of Unentanglement (Extended Abstract)

Scott Aaronson, Salman Beigi, Andrew Drucker +2 more

The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k) = QMA(2) for k ≥ 2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. • We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given Õ (√n) unentangled quantum witnesses with O (log n) qubits each. Our protocol relies on Dinur’s version of the PCP Theorem and is inherently non-relativizing. • We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k) = QMA(2) for all k ≥ 2. • We give evidence that QMA(2) ⊆ PSPACE, by showing that this would follow from “strong amplification” of QMA(2) protocols. • We prove the nonexistence of “perfect disentanglers” for simulating multiple Merlins with one.

•Jan 1, 2008•0 citations

The Power of Unentanglement

Scott Aaronson, Salman Beigi, Andrew Drucker +2 more

The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k)=QMA(2) for kges2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. *We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given O tilde(radicn) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on Dinur's version of the PCP Theorem and is inherently non-relativizing. *We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all kges=2. *We give evidence that QMA(2) sube PSPACE, by showing that this would follow from "strong amplification" of QMA(2) protocols. *We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•31 citations

Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs

Masayuki Miyamoto

We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$, \[ \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). \] Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have \[ \mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse \[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. \] Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.

quant-pharXiv:2608.07986•Aug 11, 2026•0 citations

The Power of Unentanglement

Scott Aaronson, Salman Beigi, Andrew Drucker +2 more

The class $\mathsf{QMA}( k) $, introduced by Kobayashi et al., consists of all languages that can be verified using $k$ unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that $k$ quantum proofs are more powerful than one? Does $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for $k\geq2$? Can $\mathsf{QMA}( k) $ protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. We give a protocol by which a verifier can be convinced that a 3SAT formula of size $m$ is satisfiable, with constant soundness, given $\widetilde{O}(\sqrt{m}) $ unentangled quantum witnesses with $O( \log m) $ qubits each. Our protocol relies on the existence of very short PCPs. We show that assuming a weak version of the Additivity Conjecture from quantum information theory, any $\mathsf{QMA}( 2) $ protocol can be amplified to exponentially small error, and $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for all $k\geq2$. We prove the nonexistence of “perfect disentanglers” for simulating multiple Merlins with one.

arXiv:0804.0802•Theory of Computing•Jan 1, 2009•70 citations

An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers

Schwarz, Martin

We prove a deterministic exponential time upper bound for Quantum Merlin-Arthur games with k unentangled provers. This is the first non-trivial upper bound of QMA(k) better than NEXP and can be considered an exponential improvement, unless EXP=NEXP. The key ideas of our proof are to use perturbation theory to reduce the QMA(2)-complete Separable Sparse Hamiltonian problem to a variant of the Separable Local Hamiltonian problem with an exponentially small promise gap, and then to decide this instance using epsilon-net methods. Our results imply an exponential time algorithm for the Pure State N-Representability problem in quantum chemistry, which is in QMA(2), but is not known to be in QMA. We also discuss the implications of our results on the Best Separable State problem.

arXiv:1510.08447•Oct 28, 2015•2 citations
Stoquasticity, originating in sign-problem-free physical systems, gives rise to StoqMA\sf StoqMAStoqMA, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between MA\sf MAMA and AM\sf AMAM. Unentanglement similarly gives rise to QMA(2){\sf QMA}(2)QMA(2), introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes QMA\sf QMAQMA to two unentangled proofs and still has only the trivial NEXP\sf NEXPNEXP upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via StoqMA(2){\sf StoqMA}(2)StoqMA(2), the class of unentangled stoquastic Merlin--Arthur proof systems. Beyond its complexity-theoretic interest, StoqMA(2){\sf StoqMA}(2)StoqMA(2) is connected to the optimality of non-negative tensor optimization algorithms. We highlight:
  1. NP⊆StoqMA(2){\sf NP} \subseteq {\sf StoqMA}(2)NP⊆StoqMA(2) with O~(n)\widetilde{O}(\sqrt{n})O(n​)-qubit proofs and completenes 1−2−polylog(n)1-2^{-{\rm polylog}(n)}1−2−polylog(n). Conversely, the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) gives an exponential-time upper bound for StoqMA(2){\sf StoqMA}(2)StoqMA(2). Our tightened analysis shows the optimality of our protocol and the BKS algorithm under ETH.
  2. For logarithmic-size proofs, NP⊆StoqMA(2)log⁡{\sf NP} \subseteq {\sf StoqMA}(2)_{\log}NP⊆StoqMA(2)log​ with completeness 1−O(n−2)1-O(n^{-2})1−O(n−2) and vanishing gap, while StoqMA(2)log⁡⊆MA{\sf StoqMA}(2)_{\log} \subseteq {\sf MA}StoqMA(2)log​⊆MA. Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption MA=NP{\sf MA}={\sf NP}MA=NP.
  3. For StoqMA(2)1{\sf StoqMA}(2)_1StoqMA(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 QMA(2){\sf QMA}(2)QMA(2) protocols using distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework.
Interference and entanglement are among the most fundamental properties of quantum mechanics. In this work, we investigate the power of interference in the role of detecting entanglement in the context of quantum Merlin-Arthur verification. In particular, we show that unentanglement gives no additional power to stoquastic Merlin-Arthur proof systems, whose restriction to a classical gate set results in entrywise non-negative acceptance operators and non-negative optimal witnesses, therein removing destructive interference from the verification process. Our results show that for any polynomial number of unentangled witnesses k=k(n)k = k(n)k=k(n), StoqMA(k)=StoqMA. \mathsf{StoqMA}(k) = \mathsf{StoqMA}. StoqMA(k)=StoqMA. The analytic core of this result is a new non-negative de Finetti theorem for separately bosonic states. If a mixed state ρρρ is supported on the tensor product of symmetric subspaces of H1⊗R⊗H2⊗R⊗⋯⊗Hk⊗R\mathcal{H}_1^{\otimes R} \otimes \mathcal{H}_2^{\otimes R} \otimes \cdots \otimes \mathcal{H}_k^{\otimes R}H1⊗R​⊗H2⊗R​⊗⋯⊗Hk⊗R​ then there exists a separable state τττ on H1⊗⋯⊗Hk\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_kH1​⊗⋯⊗Hk​ such that Tr(M(ρH1⊗⋯⊗Hk−τ))≤2k log⁡2dim⁡(H1⊗⋯⊗Hk)R−1, \mathrm{Tr}\big(M(ρ_{\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k} - τ)\big) \le 2 \sqrt{\frac{k\, \log_2\dim(\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k)}{R-1}}, Tr(M(ρH1​⊗⋯⊗Hk​​−τ))≤2R−1klog2​dim(H1​⊗⋯⊗Hk​)​​, simultaneously for all non-negative effects MMM. For any such operator MMM, one can define the separately symmetric lift SSR(M)\mathrm{SS}_R(M)SSR​(M) whose largest eigenvalue approximates the maximum acceptance probability of MMM over product states within the same error bound. Such a lift can be approximated by a stoquastic verifier, giving that product-state constraint of StoqMA(k)\mathsf{StoqMA}(k)StoqMA(k) verifiers can be absorbed into a polynomially larger one-witness StoqMA\mathsf{StoqMA}StoqMA verification, while preserving an inverse polynomial completeness-soundness gap.
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k) = QMA(2) for k ≥ 2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. • We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given Õ (√n) unentangled quantum witnesses with O (log n) qubits each. Our protocol relies on Dinur’s version of the PCP Theorem and is inherently non-relativizing. • We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k) = QMA(2) for all k ≥ 2. • We give evidence that QMA(2) ⊆ PSPACE, by showing that this would follow from “strong amplification” of QMA(2) protocols. • We prove the nonexistence of “perfect disentanglers” for simulating multiple Merlins with one.
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k)=QMA(2) for kges2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. *We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given O tilde(radicn) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on Dinur's version of the PCP Theorem and is inherently non-relativizing. *We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all kges=2. *We give evidence that QMA(2) sube PSPACE, by showing that this would follow from "strong amplification" of QMA(2) protocols. *We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.
We study gap amplification of the class QMA+(2)\mathsf{QMA}^{+}(2)QMA+(2) characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of NEXP\mathsf{NEXP}NEXP for some small constant gap, it is equal to QMA(2)\mathsf{QMA}(2)QMA(2) for larger constant gap. This is in stark contrast to QMA(2)\mathsf{QMA}(2)QMA(2) where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness ccc and soundness sss with c−s=1/poly(n)c-s=1/\mathrm{poly}(n)c−s=1/poly(n), NEXP=QMA+(2,c,s)=QMA+(2,1−1poly(n),14+1poly(n)). \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). NEXP=QMA+(2,c,s)=QMA+(2,1−poly(n)1​,41​+poly(n)1​). Our result gives a clean complexity phase transition for QMA+(2)\mathsf{QMA}^{+}(2)QMA+(2) since we have QMAR(2)=QMA+(2,1−1poly(n),14−1poly(n)), \mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), QMAR(2)=QMA+(2,1−poly(n)1​,41​−poly(n)1​), where QMAR(2)\mathsf{QMA}^{\mathbb R}(2)QMAR(2) denotes QMA(2)\mathsf{QMA}(2)QMA(2) with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse QMAR(2)=NEXP. \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. QMAR(2)=NEXP. Our proof combines symmetric-subspace projections with the relation QMA+(1)=NEXP\mathsf{QMA}^{+}(1)=\mathsf{NEXP}QMA+(1)=NEXP of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.
The class $\mathsf{QMA}( k) $, introduced by Kobayashi et al., consists of all languages that can be verified using kkk unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that kkk quantum proofs are more powerful than one? Does $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for k≥2k\geq2k≥2? Can $\mathsf{QMA}( k) $ protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. We give a protocol by which a verifier can be convinced that a 3SAT formula of size mmm is satisfiable, with constant soundness, given $\widetilde{O}(\sqrt{m}) $ unentangled quantum witnesses with $O( \log m) $ qubits each. Our protocol relies on the existence of very short PCPs. We show that assuming a weak version of the Additivity Conjecture from quantum information theory, any $\mathsf{QMA}( 2) $ protocol can be amplified to exponentially small error, and $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for all k≥2k\geq2k≥2. We prove the nonexistence of “perfect disentanglers” for simulating multiple Merlins with one.
We prove a deterministic exponential time upper bound for Quantum Merlin-Arthur games with k unentangled provers. This is the first non-trivial upper bound of QMA(k) better than NEXP and can be considered an exponential improvement, unless EXP=NEXP. The key ideas of our proof are to use perturbation theory to reduce the QMA(2)-complete Separable Sparse Hamiltonian problem to a variant of the Separable Local Hamiltonian problem with an exponentially small promise gap, and then to decide this instance using epsilon-net methods. Our results imply an exponential time algorithm for the Pure State N-Representability problem in quantum chemistry, which is in QMA(2), but is not known to be in QMA. We also discuss the implications of our results on the Best Separable State problem.