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

Understand

A central problem in quantum computational complexity is how to prevent entanglement-assisted cheating in multi-prover interactive proof systems.

• It is well-known that the standard oracularization technique completely fails in some proof systems under the existence of prior entanglement.
• This paper studies two constructions of two-prover one-round interactive proof systems based on oracularization.
• First, it is proved that the two-prover one-round interactive proof system for PSPACE by Cai, Condon, and Lipton 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).