Limited shared entanglement does not increase power of quantum proofs
QMA(2) with Limited Shared Entanglement
Computational Complexity
Summary
Quantum Merlin-Arthur protocols involve two helpers sending quantum proofs to a verifier, usually without sharing special quantum links called entanglement. This paper shows that even if the helpers share a small, logarithmic amount of entanglement, it doesn't make the verification system any more powerful. They also explore what happens if the helpers can communicate classically while preparing proofs and find similar limits. Extending these results to larger entanglement budgets would imply surprising breakthroughs in classical vs quantum computing.
What this means in practice
- •For quantum computer architects: Design quantum verification protocols without needing to manage or limit small shared entanglement between proof providers.
- •For cryptography engineers: Assess security guarantees of quantum proof systems assuming limited entanglement resources between provers.
A theory result. No direct application yet.
Authors
Alex Della Schiava, Ranitha Mataraarachchi
Abstract
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}$.