Loading...
Please wait, while we are loading the content...
Similar Documents
Quantum multi prover interactive proofs with communicating provers extended abstract (806).
| Content Provider | CiteSeerX |
|---|---|
| Author | Ben, Michael Avinatan, Or Pilpel, Hassidim Haran |
| Abstract | Multi Prover Interactive Proof systems (MIPs) were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context raises many open problems, as there are several interesting models to consider. For example, one can study the question when the provers share entanglement or not, and the communication between the verifier and the provers is quantum or classical. While there are several partial results on the subject, so far no one presented an efficient scheme for recognizing NEXP (or NP with logarithmic communication), except for [KM03], in the case there is no entanglement (and of course no communication between the provers). We introduce another variant of Quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case—we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap. The main idea is not to bound the information the provers exchange with each other, as in the classical case, but rather to prove that any “cheating ” strategy employed by the provers has constant probability to diminish the entanglement between the verifier and the provers by a constant amount. Detecting such reduction gives us the soundness proof. Similar ideas and techniques may help help with other models of Quantum MIP, including the dual question, of non communicating provers with unlimited entanglement. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Communicating Provers Extended Abstract Quantum Multi Prover Interactive Proof Quantum Mip Many Open Problem Logarithmic Communication Main Idea Constant Amount Simple Prover Share Entanglement Quantum Context Classical Case Similar Idea Efficient Scheme Multi Prover Interactive Proof System Provers Share Entanglement Constant Completeness-soundness Gap Soundness Proof Dual Question Classical Communication Constant Probability Various Field Several Interesting Model Several Partial Result Cryptographic Context Unlimited Entanglement |
| Content Type | Text |
