Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems

Details Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems

2007-12-13

arxiv.org/abs/0712.2163v2

Physics

Quantum Physics

20 pages. v2: An incorrect statement in the abstract about the two-party case is corrected. Relation between this work and a p

Scientific paper

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. Commuting-operator provers are at least as powerful as usual isolated but prior-entangled provers, and thus, limits for commuting-operator provers immediately give limits for usual 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 3-prover 1-round binary interactive proof 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 3-prover 1-round binary-answer game is equal to 1 or at most 1-1/p(n) for some polynomial p, where n is the number of questions. This is in contrast to the 2-prover 1-round binary-answer case, where the corresponding problem is efficiently decidable. Alternatively, NEXP has a 3-prover 1-round binary interactive proof system with perfect completeness and soundness 1-2^{-poly}.

Affiliated with

Also associated with

No associations

Rating

Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-623218