Compression of quantum multi-prover interactive proofs

DOI10.1145/3055399.3055441MaRDI QIDQ4977979zbMATH OpenOpenAlexWikidataFDO

Authors Zhengfeng Ji

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.03133

zbMATH Keywords

Bell inequalitiesentanglementnonlocal gamesquantum interactive proofsquantum PCP conjecture

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: 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 indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the possibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.

Recommendations

• Classical verification of quantum proofs
• Classical verification of quantum proofs
• Interactive proofs with approximately commuting provers
• Quantum proof systems for iterated exponential time, and beyond
• Entangled games are hard to approximate

Cited in

(18)

• On the compressed-oracle technique, and post-quantum security of proofs of sequential work
• Constant-space quantum interactive proofs against multiple provers
• Reducing the number of questions in nonlocal games
• Interactive proofs with approximately commuting provers
• The set of quantum correlations is not closed
• Algorithms, bounds, and strategies for entangled XOR games
• Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision
• Nonlocal Games with Noisy Maximally Entangled States are Decidable
• Classical verification of quantum proofs
• Quantum proof systems for iterated exponential time, and beyond
• \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem
• Quantum free games
• Zero-knowledge proof systems for QMA
• On the complexity of zero gap MIP^*
• Quantum delegation with an off-the-shelf device
• The computational advantage of MIP* vanishes in the presence of noise
• The computational advantage of MIP* vanishes in the presence of noise
• The membership problem for constant-sized quantum correlations is undecidable

This page was built for publication: Compression of quantum multi-prover interactive proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977979)