Interactive proofs with approximately commuting provers

DOI10.1007/978-3-662-47672-7_29MaRDI QIDQ3448798zbMATHOpenAlexDBLPWikidataFDO

Authors Matthew Coudron, Thomas Vidick

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Quantum computation (81P68) Quantum coherence, entanglement, quantum correlations (81P40)

Abstract: The class $MI{P}^{\ast }$ of promise problems that can be decided through an interactive proof system with multiple entangled provers provides a complexity-theoretic framework for the exploration of the nonlocal properties of entanglement. Little is known about the power of this class. The only proposed approach for establishing upper bounds is based on a hierarchy of semidefinite programs introduced independently by Pironio et al. and Doherty et al. This hierarchy converges to a value that is only known to coincide with the provers' maximum success probability in a given proof system under a plausible but difficult mathematical conjecture, Connes' embedding conjecture. No bounds on the rate of convergence are known. We introduce a rounding scheme for the hierarchy, establishing that any solution to its $N$-th level can be mapped to a strategy for the provers in which measurement operators associated with distinct provers have pairwise commutator bounded by $O(el{l}^2/sqrtN)$ in operator norm, where $ell$ is the number of possible answers per prover. Our rounding scheme motivates the introduction of a variant of $MI{P}^{\ast }$, called $MI{P}_{d}elt{a}^{\ast }$, in which the soundness property is required to hold as long as the commutator of operations performed by distinct provers has norm at most $delta$. Our rounding scheme implies the upper bound $MI{P}_{d}elt{a}^{\ast }subseteqDTIME(exp(exp(poly)/delt{a}^2))$. In terms of lower bounds we establish that $MI{P}_{2^{-poly}}^{\ast }$, with completeness $1$ and soundness $1-2^{-poly}$, contains $NEXP$. The relationship of $MI{P}_{d}elt{a}^{\ast }$ to $MIPstar$ has connections with the mathematical literature on approximate commutation. Our rounding scheme gives an elementary proof that the Strong Kirchberg Conjecture implies that $MIPstar$ is computable. We discuss applications to device-independent cryptography.

Recommendations

• MIP* = RE
• Compression of quantum multi-prover interactive proofs
• Quantum multiprover interactive proofs with communicating provers
• A multiprover interactive proof system for the local Hamiltonian problem (extended abtract)
• Entangled games are hard to approximate

Cites work

• scientific article; zbMATH DE number 3855793 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Almost Commuting Unitary Matrices
• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• Classification of injective factors. Cases \(\mathrm{II}_1\), \(\mathrm{II}_\infty\), \(\mathrm{III}_\lambda\), \(\lambda\neq 1\)
• Connes' embedding problem and Tsirelson's problem
• Interactive proofs and the hardness of approximating cliques
• More randomness from the same data
• Non-deterministic exponential time has two-prover interactive protocols
• On non-semisplit extensions, tensor products and exactness of group \(C^*\)-algebras
• Private randomness expansion with untrusted devices
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Proposed experiment to test local hidden-variable theories
• Quantum multi-prover interactive proof systems with limited prior entanglement.
• Three-player entangled XOR games are NP-hard to approximate
• Tsirelson's problem and asymptotically commuting unitary matrices
• Unique games with entangled provers are easy

Cited in

(13)

• scientific article; zbMATH DE number 176510 (Why is no real title available?)
• scientific article; zbMATH DE number 7563815 (Why is no real title available?)
• Compression of quantum multi-prover interactive proofs
• Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision
• Succinct interactive oracle proofs: applications and limitations
• Quantum multiprover interactive proofs with communicating provers
• scientific article; zbMATH DE number 1024045 (Why is no real title available?)
• Constant-Round Interactive Proof Systems for AC0[2] and NC1
• From operator algebras to complexity theory and back
• Doubly efficient interactive proofs over infinite and non-commutative rings
• On the complexity of interactive proofs with bounded communication
• Interactive proofs and the hardness of approximating cliques
• Quantum proof systems for iterated exponential time, and beyond

This page was built for publication: Interactive proofs with approximately commuting provers

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