A Caltech Library Service

Interactive Proofs with Approximately Commuting Provers

Coudron, Matthew and Vidick, Thomas (2015) Interactive Proofs with Approximately Commuting Provers. In: Automata, Languages, and Programming. Lecture Notes in Computer Science. No.9134. Springer , Heidelberg, pp. 355-366. ISBN 978-3-662-47671-0.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The class MIP∗ 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. Very little is known in terms of 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. in 2006. This hierarchy converges to a value, the field-theoretic 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(ℓ^2/√N) in operator norm, where ℓ is the number of possible answers per prover. Our rounding scheme motivates the introduction of a variant of quantum multiprover interactive proof systems, called MIP∗_δ in which the soundness property is required to hold against provers allowed to operate on the same Hilbert space as long as the commutator of operations performed by distinct provers has norm at most δ. Our rounding scheme implies the upper bound MIP∗_δ ⊆ DTIME(exp(exp(poly)/δ^2)). In terms of lower bounds we establish that MIP∗_(2−poly) contains NEXP with completeness 1 and soundness 1−2^(−poly). We discuss connections with the mathematical literature on approximate commutation and applications to device-independent cryptography.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2015 Springer-Verlag Berlin Heidelberg.
Series Name:Lecture Notes in Computer Science
Issue or Number:9134
Record Number:CaltechAUTHORS:20151207-141218015
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:62657
Deposited By: Tony Diaz
Deposited On:08 Dec 2015 21:28
Last Modified:10 Nov 2021 23:05

Repository Staff Only: item control page