Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Quantum Multi-prover Interactive Proof Systems with Limited Prior Entanglement

Hirotada Kobayashi, Keiji Matsumoto

Published Jan 1, 2002• 5 citations
Publisher
DOI
10.1007/3-540-36136-7_11

Related papers

Quantum multi-prover interactive proof systems with limited prior entanglement

Hirotada Kobayashi, Keiji Matsumoto

arXiv:cs/0102013•Journal of Computer and System Sciences•May 1, 2003•96 citations

Using Entanglement in Quantum Multi-Prover Interactive Proofs

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto +1 more

arXiv:0711.3715•Computational Complexity•Jun 1, 2009•48 citations

Parallelization of entanglement-resistant multi-prover interactive proofs

Tsuyoshi Ito

Information Processing Letters•May 20, 2014•5 citations

Quantum Two Provers Interactive Proof Systems

Beverly Sackler, Alex Rapaport

•Jan 1, 2007•0 citations

On the Power of Quantum, One Round, Two Prover Interactive Proof Systems

Alex Rapaport, Amnon Ta‐Shma

arXiv:0707.1136•Quantum Information Processing•Nov 16, 2007•2 citations

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

Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda +2 more

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.2163•IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•30 citations
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.