Entanglement-resistant two-Prover interactive proof systems and non-adaptive PIRs (pp0648-0656)
          Richard Cleve, Dmitry Gavinsky, and Rahul Jain
          doi: https://doi.org/10.26421/QIC9.7-8-7
Abstracts: We show that every language in NP is recognized by a two-prover interactive proof system with the following properties. The proof system is entanglement-resistant (i.e., its soundness is robust against provers who have prior shared entanglement), it has one round of interaction, the provers’ answers are single bits, and the completeness-soundness gap is constant (formally, NP belongs to +MIP^*_{1−ε,1/2+ε} [2], for any ε such that 0 < ε < 1/4). Our result is based on the “oracularizing” property of a particular private information retrieval scheme (PIR), and it suggests that investigating related properties of other PIRs might bear further fruit.
Key words: Quantum computing, interactive proof systems, entanglement