[QIP-Sem] QIP seminar, Mon 10/6, 4:15 pm, 36-428, Hassidim, Avinatan

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 10/6 at 4:15 pm in 36-428
-------------------------------------------------

 Hassidim,Avinatan (MIT)

Quantum Multi Prover Interactive Proofs with Communicating Provers

Abstract:

Quantum Multi Prover Interactive Proofs (QMIP) can provide us with
important insights to the capabilities of entanglement. The talk will
present some known models and insights they give. We introduce a variant of the
model, 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.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem