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• 0 citations• Revised Jul 12, 2026 (v2)
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 ${\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. 3. 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 \emph{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.

Comments
84 pages, 2 figures, 7 protocols, and 2 algorithms. Abstract shortened due to the arXiv length restriction. v2: added the results 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•0 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

Quantum Free Games

Anand Natarajan, Tina Zhang

The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC’14). In the quantum world, there are two complexity classes that can be considered quantum analogues of classical free games: (1) AM*, the multiprover interactive proof class corresponding to free games with entangled players, and, somewhat less obviously, (2) BellQMA(2), the class of quantum Merlin-Arthur proof systems with two unentangled Merlins, whose proof states are separately measured by Arthur. In this work, we make significant progress towards a tight characterization of both of these classes. (1) We show a BellQMA(2) protocol for 3SAT on n variables, where the total amount of communication is Õ(√n). This answers an open question of Chen and Drucker (2010) and also shows, conditional on ETH, that the algorithm of Brandão, Christandl and Yard (STOC’11) for optimizing over separable states is tight up to logarithmic factors. (2) We show that AM* with nprovers = 2, question length O(1), and answer-length log(n) is equal to RE, i.e. that free entangled games with constant-sized questions are as powerful as general entangled games. (In contrast, Aaronson, Impagliazzo and Moshkovitz show that classical free games are much weaker than general classical games.) We show this using a question “hyper-compression” theorem that iteratively applies the introspection technique of Ji et al. (2020). Our result is a significant improvement over the headline result of Ji et al., whose MIP* protocol for the halting problem has (n)-sized questions and answers. (3) By the same techniques, we obtain a zero-gap AM* protocol for a Π2 complete language with constant-size questions and almost logarithmically (O(logn · log* n)) large answers, improving on the headline result of Mousavi, Nezhadi and Yuen (STOC’22). (4) Using a connection to the nonuniform complexity of the halting problem we show that any MIP* protocol for RE requires Ω(logn) bits of communication. It follows that our results in item 3 are optimal up to an O(log* n) factor, and that the gapless compression theorems of Mousavi, Nezhadi and Yuen are asymptotically optimal. We conjecture that these bounds can be saturated in the gapped case as well.

arXiv:2302.04322•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•5 citations

The Complexity of Stoquastic Sparse Hamiltonians

Alex B. Grilo, Marios Rozos

Despite having an unnatural definition, $\mathsf{StoqMA}$ plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of $\mathsf{NP}$, $\mathsf{MA}$ and $\mathsf{AM}$. Therefore, understanding the exact power of $\mathsf{StoqMA}$ (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem ($\mathsf{StoqSH}$) is in $\mathsf{StoqMA}$. Since Stoquastic Local Hamiltonians are $\mathsf{StoqMA}$-hard, this implies that $\mathsf{StoqSH}$ is $\mathsf{StoqMA}$-complete. We complement this result by showing that the separable version of $\mathsf{StoqSH}$ is $\mathsf{StoqMA}(2)$-complete, where $\mathsf{StoqMA}(2)$ is the version of $\mathsf{StoqMA}$ that receives two unentangled proofs.

cs.CCCross-listedarXiv:2605.02845•May 5, 2026•0 citations

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes

Fernando Granha Jeronimo, Pei Wu

Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.

arXiv:2402.18790•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•5 citations

The QMA(2) UniverseComplexity, Entanglement, and Optimization

Fernando Granha Jeronimo, Pei Wu, Itai Leigh

The complexity class QMA(2), featuring two unentangled quantum provers, occupies a central yet poorly understood position in quantum complexity theory. While superficially a modest extension of QMA, unentanglement fundamentally changes both the algorithmic and complexitytheoretic landscape, connecting QMA(2) to deep questions in separability testing, polynomial optimization, and hardness of approximation. Over the past two decades, QMA(2) has inspired a rich body of work spanning restricted verification models, semidefinite and Sum-of-Squares hierarchies, and surprising links to classical problems such as the Unique Games Conjecture. This survey provides an overview of these developments, emphasizing structural insights, algorithmic techniques, and known barriers, while highlighting how progress on QMA(2) continues to illuminate the interplay between quantum information, convex optimization, and classical complexity theory.

ACM SIGACT News•Mar 31, 2026•0 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 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.
  3. 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 \emph{exponentially} shorter unentangled proofs even under the assumption MA=NP{\sf MA}={\sf NP}MA=NP.
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.
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 complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC’14). In the quantum world, there are two complexity classes that can be considered quantum analogues of classical free games: (1) AM*, the multiprover interactive proof class corresponding to free games with entangled players, and, somewhat less obviously, (2) BellQMA(2), the class of quantum Merlin-Arthur proof systems with two unentangled Merlins, whose proof states are separately measured by Arthur. In this work, we make significant progress towards a tight characterization of both of these classes. (1) We show a BellQMA(2) protocol for 3SAT on n variables, where the total amount of communication is Õ(√n). This answers an open question of Chen and Drucker (2010) and also shows, conditional on ETH, that the algorithm of Brandão, Christandl and Yard (STOC’11) for optimizing over separable states is tight up to logarithmic factors. (2) We show that AM* with nprovers = 2, question length O(1), and answer-length log(n) is equal to RE, i.e. that free entangled games with constant-sized questions are as powerful as general entangled games. (In contrast, Aaronson, Impagliazzo and Moshkovitz show that classical free games are much weaker than general classical games.) We show this using a question “hyper-compression” theorem that iteratively applies the introspection technique of Ji et al. (2020). Our result is a significant improvement over the headline result of Ji et al., whose MIP* protocol for the halting problem has (n)-sized questions and answers. (3) By the same techniques, we obtain a zero-gap AM* protocol for a Π2 complete language with constant-size questions and almost logarithmically (O(logn · log* n)) large answers, improving on the headline result of Mousavi, Nezhadi and Yuen (STOC’22). (4) Using a connection to the nonuniform complexity of the halting problem we show that any MIP* protocol for RE requires Ω(logn) bits of communication. It follows that our results in item 3 are optimal up to an O(log* n) factor, and that the gapless compression theorems of Mousavi, Nezhadi and Yuen are asymptotically optimal. We conjecture that these bounds can be saturated in the gapped case as well.
Despite having an unnatural definition, StoqMA\mathsf{StoqMA}StoqMA plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of NP\mathsf{NP}NP, MA\mathsf{MA}MA and AM\mathsf{AM}AM. Therefore, understanding the exact power of StoqMA\mathsf{StoqMA}StoqMA (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem (StoqSH\mathsf{StoqSH}StoqSH) is in StoqMA\mathsf{StoqMA}StoqMA. Since Stoquastic Local Hamiltonians are StoqMA\mathsf{StoqMA}StoqMA-hard, this implies that StoqSH\mathsf{StoqSH}StoqSH is StoqMA\mathsf{StoqMA}StoqMA-complete. We complement this result by showing that the separable version of StoqSH\mathsf{StoqSH}StoqSH is StoqMA(2)\mathsf{StoqMA}(2)StoqMA(2)-complete, where StoqMA(2)\mathsf{StoqMA}(2)StoqMA(2) is the version of StoqMA\mathsf{StoqMA}StoqMA that receives two unentangled proofs.
Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.
The complexity class QMA(2), featuring two unentangled quantum provers, occupies a central yet poorly understood position in quantum complexity theory. While superficially a modest extension of QMA, unentanglement fundamentally changes both the algorithmic and complexitytheoretic landscape, connecting QMA(2) to deep questions in separability testing, polynomial optimization, and hardness of approximation. Over the past two decades, QMA(2) has inspired a rich body of work spanning restricted verification models, semidefinite and Sum-of-Squares hierarchies, and surprising links to classical problems such as the Unique Games Conjecture. This survey provides an overview of these developments, emphasizing structural insights, algorithmic techniques, and known barriers, while highlighting how progress on QMA(2) continues to illuminate the interplay between quantum information, convex optimization, and classical complexity theory.