arXiv:2609.39668
QMA(2) with Limited Shared Entanglement
Alex Della Schiava, Ranitha Mataraarachchi
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.
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