On the Power of Entangled Provers: Immunizing games against entanglement
Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick · arXiv (Cornell University) · 2007
We describe two generic ways to make multi-prover classical games resistant against entangled provers. The first uses quantum communication and a quantum verifier, the second adds an additional prover. This leads to several new results on the power of proof systems with entangled provers. We show that NEXP ⊆ QMIP1,s(2, 1) and NEXP ⊆ MIP1,s(3, 1) with soundness s = 1− 2− poly(n) and PSPACE ⊆ MIP1,s(2, 1) with soundness s = 1 − 1/ poly(n), providing the first non-trivial bounds in this setting. Moreover, our results imply that, unless P = NP, the value of entangled prover games cannot be computed by semi-definite programs that are polynomial in the size of the verifier’s system, a method that has been successful for more restricted quantum games. ∗also at CNRS & LRI, Univerite de Paris-Sud, Orsay, France †Partially supported by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848 and by an Alon Fellowship of the Israeli Higher Council of Academic Research. ‡Part of this work was completed at Caltech. Supported by the National Science Foundation under Grants PHY-0456720 and CCF-0524828, by EU project QAP, and by NWO VICI project 639-023-302. Part of this research has been funded by the Dutch BSIK/BRICKS project. §Work partly done while at LRI, Univ. de Paris-Sud, Orsay.