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.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.

Apr 23, 200710 citations

Non-Signaling Proofs with O(√log n) Provers is in PSPACE

Dhiraj Holden, Yael Tauman Kalai

Non-signaling proofs, motivated by quantum computation, have found applications in cryptography and hardness of approximation. An important open problem is characterizing the power of no-signaling proofs. It is known that 2-prover no-signaling proofs are characterized by PSPACE, and that no-signaling proofs with poly(n)-provers are characterized by EXP. However, the power of k-prover no-signaling proofs, for 2kpoly(n) remained an open problem. We show that k-prover no-signaling proofs (with negligible soundness) for k=O(√logn) are contained in PSPACE. We prove this via two different routes that are of independent interest. In both routes we consider a relaxation of no-signaling called sub-no-signaling. Our main technical contribution (which is used in both our proofs) is a reduction showing how to convert any sub-no-signaling strategy with value at least 1−2−Ω(k2) into a no-signaling one with value at least 2−O(k2). In the first route, we show that the classical prover reduction method for converting k-prover games into 2-prover games carries over to the no-signaling setting with the following loss in soundness: if a k-player game has value less than 2−ck2 (for some constant~c>0), then the corresponding 2-prover game has value at most 1−2dk2 (for some constant~d>0). In the second route we show that the value of a sub-no-signaling game can be approximated in space that is polynomial in the communication complexity and exponential in the number of provers.Non-signaling proofs, motivated by quantum computation, have found applications in cryptography and hardness of approximation. An important open problem is characterizing the power of no-signaling proofs. It is known that 2-prover no-signaling proofs are characterized by PSPACE, and that no-signaling proofs with poly(n)-provers are characterized by EXP. However, the power of k-prover no-signaling proofs, for 2kpoly(n) remained an open problem. We show that k-prover no-signaling proofs (with negligible soundness) for k=O(√logn) are contained in PSPACE. We prove this via two different routes that are of independent interest. In both routes we consider a relaxation of no-signaling called sub-no-signaling. Our main technical contribution (which is used in both our proofs) is a reduction showing how to convert any sub-no-signaling strategy with value at least 1−2−Ω(k2) into a no-signaling one with value at least 2−O(k2). In the first route, we show that the classical prover reduction method for converting k-prover games into 2-prover games carries over to the no-signaling setting with the following loss in soundness: if a k-player game has value less than 2−ck2 (for some constant~c>0), then the corresponding 2-prover game has value at most 1−2dk2 (for some constant~d>0). In the second route we show that the value of a sub-no-signaling game can be approximated in space that is polynomial in the communication complexity and exponential in the number of provers.

Jun 1, 20200 citations

Polynomial-Space Approximation of No-Signaling Provers

Tsuyoshi Ito

arXiv:0908.2363Lecture notes in computer scienceJan 1, 201029 citations

A K-Provers Parallel Repetition Theorem for a Version of No-Signaling Model

Ricky Rosen

Lecture notes in computer scienceJan 1, 20104 citations

How to Delegate Computations: The Power of No-Signaling Proofs

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t = t ( n ), where the running time of the prover is poly ( t ) and the running time of the verifier is n · polylog ( t ). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval ( PIR ) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies , a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t ( n ), we construct a multi-prover interactive proof ( MIP ), that is, sound against no-signaling strategies, where the running time of the provers is poly ( t ), the number of provers is polylog ( t ), and the running time of the verifier is n · polylog ( t ). In particular, this shows that the class of languages that have polynomial-time MIP s that are sound against no-signaling strategies, is exactly EXP . Previously, this class was only known to contain PSPACE . To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al. (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t = t ( n ), where the running time of the prover is poly ( t ) and the running time of the verifier is n · polylog ( t ). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval ( PIR ) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies , a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t ( n ), we construct a multi-prover interactive proof ( MIP ), that is, sound against no-signaling strategies, where the running time of the provers is poly ( t ), the number of provers is polylog ( t ), and the running time of the verifier is n · polylog ( t ). In particular, this shows that the class of languages that have polynomial-time MIP s that are sound against no-signaling strategies, is exactly EXP . Previously, this class was only known to contain PSPACE . To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al. (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.

Journal of the ACMNov 29, 202116 citations

Non-Signaling Proofs with

O(\sqrt{\log n})

Provers are in PSPACE

poly(n)

-provers are characterized by EXP. However, the power of

k

-prover no-signaling proofs, for

20

), then the corresponding 2-prover game has value at most

1 - 2^{dk^2}

(for some constant~

d>0

). In the second route we show that the value of a sub-no-signaling game can be approximated in space that is polynomial in the communication complexity and exponential in the number of provers.