Compression of quantum multi-prover interactive proofs

DOI10.1145/3055399.3055441zbMATH Open1370.68102arXiv1610.03133OpenAlexW2530940551WikidataQ130919693 ScholiaQ130919693MaRDI QIDQ4977979FDOQ4977979

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)

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.

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

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

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)

Cited In (13)

• 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
• Title not available (Why is that?)
• 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
• The set of quantum correlations is not closed
• Quantum free games
• Reducing the number of questions in nonlocal 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
• Classical verification of quantum proofs

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)