Zhengfeng Ji (UT Sydney)
March 15, 2017
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.