log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Quantum-Proofs.zip
Zhengfeng Ji - UT Sydney
Wednesday, March 15, 2017, 11:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract
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.
This talk is organized by Javiera Caceres