Interactive proofs with approximately commuting provers
The class MIP∗ of promise problems that can be decided through an interactive proof system withmultiple 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(l2/ √ N) in operator norm, where l 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.
Cite this item
Coudron, M., & Vidick, T. (2015). Interactive proofs with approximately commuting provers. In M. M. Halldorsson, N. Kobayashi, B. Speckmann, & K. Iwama (Editors), 42nd International Colloquium on Automata, Languages and Programming (ICALP2015). https://doi.org/10.1007/978-3-662-47672-7_29
Click Copy to copy the citation, or select the text manually.
2-s2.0-84950112462
Massachusetts Institute of Technology
California Institute of Technology
2015
Berlin, Heidelberg
9783662476710
9783662476727
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 9134
1611-3349
0302-9743
355
366
REVIEWED
OTHER
| Event name | Event acronym | Event place | Event date |
ICALP2015 | Kyoto, Japan | 2015-07-06 - 2015-07-10 | |