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

Subscribe to A Quantum Bit 

Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...

Sign Up Now

Sign up to receive A Quantum Bit in your email!

 Have an idea for A Quantum Bit? Submit your suggestions to