RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

March 15, 2017 - 11:00am
Zhengfeng Ji
UT Sydney
In this talk, I will unzip a recent progress on quantum
interactive proofs---communications in quantum multi-prover
interactive proofs can be exponentially compressed. By combining
several old good ideas in quantum proofs, we will show how to
construct a protocol that transforms any quantum multi-prover
interactive proof system into a nonlocal game, a scaled-down version
the proof system in which questions consist of a logarithmic number of
bits and answers of a constant number of bits. As a corollary, this
proves that nonlocal games are complete for QMIP*, and therefore
NEXP-hard. This establishes that nonlocal games are provably harder
than classical games. Our result reveals an important difference
between classical and quantum multi-prover proofs, and makes
interesting implications for the multi-prover variant of the quantum
PCP conjecture.
CSS 3100A