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:2609.39668

QMA(2) with Limited Shared Entanglement

Alex Della Schiava, Ranitha Mataraarachchi

quant-phcs.CCSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations• Revised Oct 14, 2026 (v3)
v1 · Sep 30, 2026v2 · Oct 13, 2026v3 · Oct 14, 2026
arXivHTMLPDF

Abstract

In $\mathsf{QMA}(2)$, two computationally unbounded provers submit unentangled quantum witnesses to a polynomial-time quantum verifier. We ask whether allowing limited shared entanglement between the two provers changes the power of $\mathsf{QMA}(2)$. To this end, we formalize $\mathsf{QMA}(2;h)$, a variant in which the provers initially share $h$ EPR pairs, as suggested by Aaronson, Beigi, Drucker, Fefferman, and Shor (ToC~2009). We show that polynomially many shared EPR pairs give the provers no cheating advantage: $\mathsf{QMA}(2)\subseteq\mathsf{QMA}(2;h)$ for $h=\operatorname{poly}(n)$. For logarithmically many pairs, the power of $\mathsf{QMA}(2)$ remains unchanged, strengthening this inclusion to $\mathsf{QMA}(2)=\mathsf{QMA}(2;h)$ for $h=O(\log n)$. Finally, we introduce a variant that also allows classical communication between the provers when preparing the witnesses. This setting is particularly revealing for logarithmic-size witnesses: assuming $\mathsf{NP}\nsubseteq\mathsf{BQP}$, we show that superlogarithmically many shared EPR pairs strictly reduce the model's computational power.

AI Summary

The paper asks how relaxing the unentanglement promise affects $\mathsf{QMA}(2)$. It formalizes $\mathsf{QMA}(2;h)$, where the provers prepare witnesses by local channels from $h$ shared EPR pairs, and an LOCC variant whose legal witnesses are exactly states of Schmidt number at most $2^h$. Without communication, legal pure witnesses have equal nonzero Schmidt coefficients, but mixed witnesses need not decompose into legal pure witnesses. For polynomially bounded $h\le H$, it proves $\mathsf{QMA}(2;h)\subseteq\mathsf{QMA}(2;H)$, also for LOCC preparation. The adapted verifier requests the surplus EPR pairs and projects them onto Bell states; this preserves the optimal acceptance probability exactly. The main equality is $\mathsf{QMA}(2;h)=\mathsf{QMA}(2)$ for $h=O(\log n)$, again including LOCC. The reverse simulation encodes local Schmidt bases in unentangled witnesses, uses SWAP tests to enforce consistency and maximally mixed index registers, and reconstructs the original witness through Bell projection. Four witnesses suffice, with gap $\Omega(\Delta^2/[D(1+\Delta D)])$, where $D=2^h$ and $\Delta$ is the original gap; Harrow–Montanaro reduction and amplification finish the simulation. With logarithmic-size witnesses and inverse-polynomial gaps, the equalities persist. For superlogarithmic shared entanglement, the LOCC model instead equals $\mathsf{BQP}$, hence is strictly weaker than $\mathsf{QMA}_{\log}(2)$ assuming $\mathsf{NP}\nsubseteq\mathsf{BQP}$. Equality for polynomial entanglement budgets remains open: Bell reconstruction succeeds with probability $D^{-2}$, limiting the simulation. Whether the logarithmic-witness collapse also holds without communication remains unresolved.

Almost certainly largely AI-generatedAI use disclosed
OpenAI's GPT-5.6 Sol and GPT-6 Astra (via ChatGPT), together with Anthropic's Claude 5.0 Opus, contributed substantially to both the research and the manuscript.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
27 pages (including appendices), 1 table, 0 figures. v3: updated arXiv metadata

Related papers

Reducing Provers in Distributed Quantum Verification

Alex Della Schiava, Atsuya Hasegawa, François Le Gall +1 more

In the distributed quantum Merlin-Arthur ($\mathsf{dQMA}$) model introduced by Fraigniaud, Le Gall, Nishimura, and Paz (ITCS 2021), a network of quantum computers verifies a global property with the aid of a quantum proof supplied by an untrusted prover. While the nodes are computationally unbounded, the challenge is to limit proof size and the communication required for verification. In this paper, we consider the model of Hasegawa, Kundu, and Nishimura (PODC 2024), where the proof must be unentangled across nodes, and define its extension to $k$ unentangled provers, denoted by $\mathsf{dQMAS}(k)$. In this setting, we investigate the proof size per node and the communication costs of reducing the number of provers. Our first result reduces the number of provers from $k$ to two, doubling the proof size without additional communication. Moreover, with four additional rounds, we can reduce the number of provers from $k$ to one, using at most three times the original local proof size plus a logarithmic term in the number of nodes. Finally, we establish amplification for perfectly complete protocols. In this regime, a single prover suffices with a constant-factor overhead in our reductions, yielding $\mathsf{dQMAS} = \mathsf{dQMAS}(k)$.

arXiv:2611.12600•Nov 9, 2026•0 citations

NP vs QMA_\log(2)

Salman Beigi

Although it is believed unlikely that $\NP$-hard problems admit efficient quantum algorithms, it has been shown that a quantum verifier can solve NP-complete problems given a "short" quantum proof; more precisely, NP\subseteq QMA_{\log}(2) where QMA_{\log}(2) denotes the class of quantum Merlin-Arthur games in which there are two unentangled provers who send two logarithmic size quantum witnesses to the verifier. The inclusion NP\subseteq QMA_{\log}(2) has been proved by Blier and Tapp by stating a quantum Merlin-Arthur protocol for 3-coloring with perfect completeness and gap 1/24n^6. Moreover, Aaronson et al. have shown the above inclusion with a constant gap by considering $\widetilde{O}(\sqrt{n})$ witnesses of logarithmic size. However, we still do not know if QMA_{\log}(2) with a constant gap contains NP. In this paper, we show that 3-SAT admits a QMA_{\log}(2) protocol with the gap 1/n^{3+\epsilon}} for every constant \epsilon>0.

arXiv:0810.5109•Quantum Information and Computation•Jan 1, 2010•36 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•5 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•16 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

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
In QMA(2)\mathsf{QMA}(2)QMA(2), two computationally unbounded provers submit unentangled quantum witnesses to a polynomial-time quantum verifier. We ask whether allowing limited shared entanglement between the two provers changes the power of QMA(2)\mathsf{QMA}(2)QMA(2). To this end, we formalize QMA(2;h)\mathsf{QMA}(2;h)QMA(2;h), a variant in which the provers initially share hhh EPR pairs, as suggested by Aaronson, Beigi, Drucker, Fefferman, and Shor (ToC~2009). We show that polynomially many shared EPR pairs give the provers no cheating advantage: QMA(2)⊆QMA(2;h)\mathsf{QMA}(2)\subseteq\mathsf{QMA}(2;h)QMA(2)⊆QMA(2;h) for h=poly⁡(n)h=\operatorname{poly}(n)h=poly(n). For logarithmically many pairs, the power of QMA(2)\mathsf{QMA}(2)QMA(2) remains unchanged, strengthening this inclusion to QMA(2)=QMA(2;h)\mathsf{QMA}(2)=\mathsf{QMA}(2;h)QMA(2)=QMA(2;h) for h=O(log⁡n)h=O(\log n)h=O(logn). Finally, we introduce a variant that also allows classical communication between the provers when preparing the witnesses. This setting is particularly revealing for logarithmic-size witnesses: assuming NP⊈BQP\mathsf{NP}\nsubseteq\mathsf{BQP}NP⊈BQP, we show that superlogarithmically many shared EPR pairs strictly reduce the model's computational power.
The paper asks how relaxing the unentanglement promise affects QMA(2)\mathsf{QMA}(2)QMA(2). It formalizes QMA(2;h)\mathsf{QMA}(2;h)QMA(2;h), where the provers prepare witnesses by local channels from hhh shared EPR pairs, and an LOCC variant whose legal witnesses are exactly states of Schmidt number at most 2h2^h2h. Without communication, legal pure witnesses have equal nonzero Schmidt coefficients, but mixed witnesses need not decompose into legal pure witnesses.
For polynomially bounded h≤Hh\le Hh≤H, it proves QMA(2;h)⊆QMA(2;H)\mathsf{QMA}(2;h)\subseteq\mathsf{QMA}(2;H)QMA(2;h)⊆QMA(2;H), also for LOCC preparation. The adapted verifier requests the surplus EPR pairs and projects them onto Bell states; this preserves the optimal acceptance probability exactly. The main equality is QMA(2;h)=QMA(2)\mathsf{QMA}(2;h)=\mathsf{QMA}(2)QMA(2;h)=QMA(2) for h=O(log⁡n)h=O(\log n)h=O(logn), again including LOCC. The reverse simulation encodes local Schmidt bases in unentangled witnesses, uses SWAP tests to enforce consistency and maximally mixed index registers, and reconstructs the original witness through Bell projection. Four witnesses suffice, with gap Ω(Δ2/[D(1+ΔD)])\Omega(\Delta^2/[D(1+\Delta D)])Ω(Δ2/[D(1+ΔD)]), where D=2hD=2^hD=2h and Δ\DeltaΔ is the original gap; Harrow–Montanaro reduction and amplification finish the simulation.
With logarithmic-size witnesses and inverse-polynomial gaps, the equalities persist. For superlogarithmic shared entanglement, the LOCC model instead equals BQP\mathsf{BQP}BQP, hence is strictly weaker than QMAlog⁡(2)\mathsf{QMA}_{\log}(2)QMAlog​(2) assuming NP⊈BQP\mathsf{NP}\nsubseteq\mathsf{BQP}NP⊈BQP. Equality for polynomial entanglement budgets remains open: Bell reconstruction succeeds with probability D−2D^{-2}D−2, limiting the simulation. Whether the logarithmic-witness collapse also holds without communication remains unresolved.
In the distributed quantum Merlin-Arthur (dQMA\mathsf{dQMA}dQMA) model introduced by Fraigniaud, Le Gall, Nishimura, and Paz (ITCS 2021), a network of quantum computers verifies a global property with the aid of a quantum proof supplied by an untrusted prover. While the nodes are computationally unbounded, the challenge is to limit proof size and the communication required for verification. In this paper, we consider the model of Hasegawa, Kundu, and Nishimura (PODC 2024), where the proof must be unentangled across nodes, and define its extension to kkk unentangled provers, denoted by dQMAS(k)\mathsf{dQMAS}(k)dQMAS(k). In this setting, we investigate the proof size per node and the communication costs of reducing the number of provers. Our first result reduces the number of provers from kkk to two, doubling the proof size without additional communication. Moreover, with four additional rounds, we can reduce the number of provers from kkk to one, using at most three times the original local proof size plus a logarithmic term in the number of nodes. Finally, we establish amplification for perfectly complete protocols. In this regime, a single prover suffices with a constant-factor overhead in our reductions, yielding dQMAS=dQMAS(k)\mathsf{dQMAS} = \mathsf{dQMAS}(k)dQMAS=dQMAS(k).
Although it is believed unlikely that $\NP$-hard problems admit efficient quantum algorithms, it has been shown that a quantum verifier can solve NP-complete problems given a "short" quantum proof; more precisely, NP\subseteq QMA_{\log}(2) where QMA_{\log}(2) denotes the class of quantum Merlin-Arthur games in which there are two unentangled provers who send two logarithmic size quantum witnesses to the verifier. The inclusion NP\subseteq QMA_{\log}(2) has been proved by Blier and Tapp by stating a quantum Merlin-Arthur protocol for 3-coloring with perfect completeness and gap 1/24n^6. Moreover, Aaronson et al. have shown the above inclusion with a constant gap by considering O~(n)\widetilde{O}(\sqrt{n})O(n​) witnesses of logarithmic size. However, we still do not know if QMA_{\log}(2) with a constant gap contains NP. In this paper, we show that 3-SAT admits a QMA_{\log}(2) protocol with the gap 1/n^{3+\epsilon}} for every constant \epsilon>0.
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.
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 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.
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.