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

arXiv:0908.2363 · Lecture notes in computer science

Polynomial-Space Approximation of No-Signaling Provers

Tsuyoshi Ito

Published Jan 1, 2010• 30 citations
arXivHTMLPDF
DOI
10.1007/978-3-642-14165-2_13

Related papers

Multi-prover Commitments Against Non-signaling Attacks

Serge Fehr, Max Fillinger

Lecture notes in computer science•Jan 1, 2015•8 citations

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

Ricky Rosen

Lecture notes in computer science•Jan 1, 2010•4 citations

Interactive Proofs with Approximately Commuting Provers

Matthew Coudron, Thomas Vidick

Lecture notes in computer science•Jan 1, 2015•3 citations

Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies

Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto

This paper presents three results on the power of two-prover one-round interactive proof systems based on oracularization under the existence of prior entanglement between dishonest provers. It is proved that the two-prover one-round interactive proof system for PSPACE by Cai, Condon, and Lipton [JCSS 48:183-193, 1994] still achieves exponentially small soundness error in the existence of prior entanglement between dishonest provers (and more strongly, even if dishonest provers are allowed to use arbitrary no-signaling strategies). It follows that, unless the polynomial-time hierarchy collapses to the second level, two-prover systems are still advantageous to single-prover systems even when only malicious provers can use quantum information. It is also shown that a "dummy" question may be helpful when constructing an entanglement-resistant multi-prover system via oracularization. This affirmatively settles a question posed by Kempe et al. [FOCS 2008, pp. 447-456] and every language in NEXP is proved to have a two-prover one-round interactive proof system even against entangled provers, albeit with exponentially small gap between completeness and soundness. In other words, it is NP-hard to approximate within an inverse-polynomial the value of a classical two-prover one-round game against entangled provers. Finally, both for the above proof system for NEXP and for the quantum two-prover one-round proof system for NEXP proposed by Kempe et al., it is proved that exponentially small completeness-soundness gaps are best achievable unless soundness analysis uses the structure of the underlying system with unentangled provers.

arXiv:0810.0693•IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•71 citations

Non-signaling proofs with o(√ log n) provers are 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 non-signaling proofs. It is known that non-signaling proofs with two provers are characterized by PSPACE and that non-signaling proofs with poly(n)-provers are characterized by EXP. However, the power of k-prover non-signaling proofs, for 2<k<(n) remained an open problem.

arXiv:1910.02590•ACM Symposium on Theory of Computing (STOC)•Jun 7, 2020•2 citations

No-signaling values of quantum games--an operator algebra perspective

Roy Araiza, Marius Junge, Carlos Palazuelos

The aim of this work is to study two-prover quantum games (i.e., games with quantum inputs and outputs) from an operator-algebraic and operator-space point of view. We characterize several notions of the value of such games by formulating them in terms of tensor norms in the category of operator spaces. The main results of the paper concern the description of the so-called no-signalling value of these games, for which we not only provide a precise operator-space formulation, but also establish close connections between this study and some problems in operator algebras. In particular, we show how the recent counterexample to Grothendieck's theorem for operator spaces given in \cite{Ara} can be understood as a direct consequence of results in quantum information theory. We also obtain new upper bounds on the gap between the no-signalling value and the quantum value of two-prover quantum games, improving the best previously known estimates.

quant-pharXiv:2606.21664•Jun 23, 2026•1 citation
This paper presents three results on the power of two-prover one-round interactive proof systems based on oracularization under the existence of prior entanglement between dishonest provers. It is proved that the two-prover one-round interactive proof system for PSPACE by Cai, Condon, and Lipton [JCSS 48:183-193, 1994] still achieves exponentially small soundness error in the existence of prior entanglement between dishonest provers (and more strongly, even if dishonest provers are allowed to use arbitrary no-signaling strategies). It follows that, unless the polynomial-time hierarchy collapses to the second level, two-prover systems are still advantageous to single-prover systems even when only malicious provers can use quantum information. It is also shown that a "dummy" question may be helpful when constructing an entanglement-resistant multi-prover system via oracularization. This affirmatively settles a question posed by Kempe et al. [FOCS 2008, pp. 447-456] and every language in NEXP is proved to have a two-prover one-round interactive proof system even against entangled provers, albeit with exponentially small gap between completeness and soundness. In other words, it is NP-hard to approximate within an inverse-polynomial the value of a classical two-prover one-round game against entangled provers. Finally, both for the above proof system for NEXP and for the quantum two-prover one-round proof system for NEXP proposed by Kempe et al., it is proved that exponentially small completeness-soundness gaps are best achievable unless soundness analysis uses the structure of the underlying system with unentangled provers.
The aim of this work is to study two-prover quantum games (i.e., games with quantum inputs and outputs) from an operator-algebraic and operator-space point of view. We characterize several notions of the value of such games by formulating them in terms of tensor norms in the category of operator spaces. The main results of the paper concern the description of the so-called no-signalling value of these games, for which we not only provide a precise operator-space formulation, but also establish close connections between this study and some problems in operator algebras. In particular, we show how the recent counterexample to Grothendieck's theorem for operator spaces given in \cite{Ara} can be understood as a direct consequence of results in quantum information theory. We also obtain new upper bounds on the gap between the no-signalling value and the quantum value of two-prover quantum games, improving the best previously known estimates.