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

Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto

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…