Interactive Proofs with Approximately Commuting Provers

Abstract

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.