AB - © 2017 ACM. 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, it follows 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 indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the feasibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.
AU - Ji, Z
DA - 2017/06/19
DO - 10.1145/3055399.3055441
EP - 302
JO - Proceedings of the Annual ACM Symposium on Theory of Computing
PY - 2017/06/19
SP - 289
TI - Compression of qantum multi-prover interactive proofs
VL - Part F128415
Y1 - 2017/06/19
Y2 - 2019/06/21
ER -