Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision.

We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is NP-complete to decide whether the classical value of a non-local game is 1 or 1 --- ∈, promised that one of the two is the case. Furthermore, as long as ∈ is small enough, this result does not depend on the gap ∈. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap ∈ decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of MIPco(2, 1, 1, s) (proofs with two provers, one round, completeness probability 1, soundness probability s, and commuting-operator strategies) can increase without bound as the gap 1 --- s gets arbitrarily small.Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class PZK-MIPcoδ (2, 1, 1, s) of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap 1 --- s gets arbitrarily small. While we do not know any computable time upper bound on the class MIPco, a result of the first author and Vidick shows that for s = 1 --- 1/poly(f(n)) and δ = 1/poly(f(n)), the class MIPcoδ (2, 1, 1, s), with constant communication from the provers, is contained in TIME(exp(poly(f(n)))). We give a lower bound of coNTIME(f(n)) (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis.