QMA(2) with Limited Shared Entanglement

A $\mathsf{Q}\mathsf{M}\mathsf{A}(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{Q}\mathsf{M}\mathsf{A}(2;h)$, a variant of $\mathsf{Q}\mathsf{M}\mathsf{A}(2)$ in which the two provers may share $h$ EPR pairs. Our main result shows that the power of $\mathsf{Q}\mathsf{M}\mathsf{A}(2)$ remains unchanged for up to logarithmically many shared EPR pairs: $\mathsf{Q}\mathsf{M}\mathsf{A}(2;h)=\mathsf{Q}\mathsf{M}\mathsf{A}(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{Q}\mathsf{M}\mathsf{A}(4)=\mathsf{Q}\mathsf{M}\mathsf{A}(2)$ (FOCS, 2010). We also prove monotonicity in the EPR budget: $\mathsf{Q}\mathsf{M}\mathsf{A}(2;h)\subseteq \mathsf{Q}\mathsf{M}\mathsf{A}(2;H)$ for $h\le H$, preserving completeness and soundness. Combined with input padding, this shows that establishing $\mathsf{Q}\mathsf{M}\mathsf{A}(2;n^{\epsilon })=\mathsf{Q}\mathsf{M}\mathsf{A}(2)$ for any fixed $\epsilon >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{N}\mathsf{P}\subseteq \mathsf{B}\mathsf{Q}\mathsf{P}$.