Metraipolis › archive › dc_f81db006aec7

QMA(2) with Limited Shared Entanglement — arXiv:2609.39668

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.39668
License (as archived)
CC0-1.0
Archived
2026-10-07T15:18:01.785Z
SHA-256 of the archived text
2415650fad5a5ab90d3af30fdf0f5eb26589626b9af135328e8109786e6c75e4
Stable URL of this page
https://metraipolis.com/documento/dc_f81db006aec7

How to cite

QMA(2) with Limited Shared Entanglement — arXiv:2609.39668 — arXiv (en), https://arxiv.org/abs/2609.39668 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f81db006aec7 (Metraipolis archive dc_f81db006aec7, sha256 2415650fad5a5ab90d3af30fdf0f5eb26589626b9af135328e8109786e6c75e4)
BibTeX
@misc{dcf81db006aec7,
  title = {QMA(2) with Limited Shared Entanglement — arXiv:2609.39668},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.39668},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f81db006aec7; sha256 2415650fad5a5ab90d3af30fdf0f5eb26589626b9af135328e8109786e6c75e4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39668. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A $\mathsf{QMA}(2)$ protocol involves two provers submitting unentangled witnesses to a polynomial-time quantum verifier. In The Power of Unentanglement (ToC, 2009), Aaronson et al. proposed $\mathsf{QMA}(2;h)$, a variant of $\mathsf{QMA}(2)$ in which the two provers may share $h$ EPR pairs. Our main result shows that the power of $\mathsf{QMA}(2)$ remains unchanged for up to logarithmically many shared EPR pairs: $\mathsf{QMA}(2;h)=\mathsf{QMA}(2)$ for $h=O(\log n)$, where $n$ is the input length. The result follows from a simulation using four unentangled witnesses, combined with the Harrow-Montanaro equality $\mathsf{QMA}(4)=\mathsf{QMA}(2)$ (FOCS, 2010). We also prove monotonicity in the EPR budget: $\mathsf{QMA}(2;h)\subseteq\mathsf{QMA}(2;H)$ for $h\le H$, preserving completeness and soundness. Combined with input padding, this shows that establishing $\mathsf{QMA}(2;n^\varepsilon)=\mathsf{QMA}(2)$ for any fixed $\varepsilon>0$ would imply equality for every polynomially bounded budget, resolving the open problem raised by Aaronson et al. Finally, we extend these results to a variant of the model in which the provers may use local operations and classical communication (LOCC) during witness preparation. For logarithmic-size witnesses and inverse-polynomial gaps, both models remain equivalent to their unentangled counterpart when $h=O(\log n)$. We show that extending this equivalence to any superlogarithmic EPR budget in the LOCC model would imply $\mathsf{NP}\subseteq\mathsf{BQP}$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.39668 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:51:27.480Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).