Interactive proofs with approximately commuting provers

DOI10.1007/978-3-662-47672-7_29zbMATH Open1441.68088DBLPconf/icalp/CoudronV15arXiv1510.00102OpenAlexW2218897312WikidataQ59792601 ScholiaQ59792601MaRDI QIDQ3448798FDOQ3448798

Authors: Matthew Coudron, Thomas Vidick 

Publication date: 27 October 2015

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

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}^{*}$, 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}^{*}$ 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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

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

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)