Algorithms and Complexity Seminar
Quantum Multi Proof System with Communicating Provers.
Avinatan Hassidim (Hebrew University, MIT)
We introduce a variant of Quantum Multi Prover Interactive Proofs (QMIP),
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
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
Joint work with Michael Ben-Or and Haran Pilpel