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

entanglementBell inequalitiesnonlocal 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

(13)

• Classical verification of quantum proofs
• Constant-space quantum interactive proofs against multiple provers
• Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision
• scientific article; zbMATH DE number 7559053 (Why is no real title available?)
• On the compressed-oracle technique, and post-quantum security of proofs of sequential work
• Interactive proofs with approximately commuting provers
• Quantum proof systems for iterated exponential time, and beyond
• Reducing the number of questions in nonlocal games
• The set of quantum correlations is not closed
• Quantum free games
• Zero-knowledge proof systems for QMA
• Nonlocal Games with Noisy Maximally Entangled States are Decidable
• \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem

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)