Duration: 30:55

481 views

10

"We present a protocol that transforms any quantum multi-prover
interactive proof into a nonlocal game in which questions consist of
logarithmic number of bits and answers of constant number of bits.
As a corollary, this proves that the promise problem corresponding to
the approximation of the nonlocal value to inverse polynomial accuracy
is complete for QMIP, and therefore NEXP-hard.
This establishes that nonlocal games are provably harder than
classical games without any complexity theory assumptions.
Our result also provides a strong negative evidence for the multi-prover
variant of the quantum PCP conjecture."