Jan 11 Matthew Coudron. 'Interactive proofs with approximately commuting provers' (Part 1)

QIP 2016, Banff, 10-16 January 2016

Date: 11 Jan 2016

Title: "Interactive proofs with approximately commuting provers"
Authors:Matthew Coudron and Thomas Vidick.

Abstract: The class \MIP∗\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 NN-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−−√)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∗δ\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))\MIPδ∗⊆\DTIME(exp⁡(exp⁡(\poly)/δ2)). In terms of lower bounds we establish that \MIP∗2−\poly\MIP2−\poly∗, with completeness 11 and soundness 1−2−\poly1−2−\poly, contains \NEXP\NEXP. The relationship of \MIP∗δ\MIPδ∗ to \MIPstar\MIPstar has connections with the mathematical literature on approximate commutation. Our rounding scheme gives an elementary proof that the Strong Kirchberg Conjecture implies that \MIP∗\MIP∗ is computable. We also discuss applications to device-independent cryptography.