Interactive proofs with approximately commuting provers
arXiv:1510.00102
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. 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 -th level can be mapped to a strategy for the provers in which measurement operators associated with distinct provers have pairwise commutator bounded by in operator norm, where is the number of possible answers per prover. Our rounding scheme motivates the introduction of a variant of $\MIP^*$, called $\MIP_δ^*$, in which the soundness property is required to hold as long as the commutator of operations performed by distinct provers has norm at most . Our rounding scheme implies the upper bound $\MIP_δ^* \subseteq \DTIME(\exp(\exp(\poly)/δ^2))$. In terms of lower bounds we establish that $\MIP^*_{2^{-\poly}}$, with completeness and soundness $1-2^{-\poly}$, contains $\NEXP$. The relationship of $\MIP_δ^*$ 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.
References in corpus (12)
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Bounding the set of quantum correlations
- Randomness vs Non Locality and Entanglement
- Connes' embedding problem and Tsirelson's problem
- Maximal violation of the I3322 inequality using infinite dimensional quantum systems
- More Randomness from the Same Data
- Security and Composability of Randomness Expansion from Bell Inequalities
- Device-Independent Randomness Generation in the Presence of Weak Cross-Talk
- Extremal quantum correlations for N parties with two dichotomic observables per site
- Tsirelson's Problem
- Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
- Three-player entangled XOR games are NP-hard to approximate