A central question in quantum information theory and computational complexity is how powerful nonlocal strategies are in cooperative games with imperfect information, such as multi-prover interactive proof systems. This paper develops a new method for proving limits of nonlocal strategies that make use of prior entanglement among players (or, provers, in the terminology of multi-prover interactive proofs). Instead of proving the limits for usual isolated provers who initially share entanglement, this paper proves the limits for "commuting-operator provers", who share private space, but can apply only such operators that are commutative with any operator applied by other provers. Obviously, these commuting-operator provers are at least as powerful as usual isolated but prior-entangled provers, and thus, limits in the model with commuting-operator provers immediately give limits in the usual model with prior-entangled provers. Using this method, we obtain an n-party generalization of the Tsirelson bound for the Clauser-Horne-Shimony-Holt inequality, for every n. Our bounds are tight in the sense that, in every n-party case, the equality is achievable by a usual nonlocal strategy with prior entanglement. We also apply our method to a three-prover one-round binary interactive proof system for NEXP. Combined with the technique developed by Kempe, Kobayashi, Matsumoto, Toner and Vidick to analyze the soundness of the proof system, it is proved to be NP-hard to distinguish whether the entangled value of a three-prover one-round binary-answer game is equal to one or at most 1-1/p(n) for some polynomial p, where n is the number of questions. This is in contrast to the two-prover one-round binary-answer case, where the corresponding problem is efficiently decidable. Alternatively, NEXP has a three-prover one-round binary interactive proof system with perfect completeness and soundness 1 middot 2-poly.

arXiv:0712.2163IEEE Conference on Computational Complexity (CCC)Jun 1, 200828 citations

Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems

Richard Cleve, Dmitry Gavinsky, Rahul Jain

We show that, for any language in NP, there is an entanglement-resistant constant-bit two-prover interactive proof system with a constant completeness vs. soundness gap. The previously proposed classical two-prover constant-bit interactive proof systems are known not to be entanglement-resistant. This is currently the strongest expressive power of any known constant-bit answer multi-prover interactive proof system that achieves a constant gap. Our result is based on an "oracularizing" property of certain private information retrieval systems, which may be of independent interest.

arXiv:0707.1729Jul 12, 200721 citations