On the complexity of zero gap MIP*
share
The class MIP^* is the set of languages decidable by multiprover interactive proofs with quantum entangled provers. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that MIP^* is equal to RE, the set of recursively enumerable languages. In particular this shows that the complexity of approximating the quantum value of a non-local game G is equivalent to the complexity of the Halting problem. In this paper we investigate the complexity of deciding whether the quantum value of a non-local game G is exactly 1. This problem corresponds to a complexity class that we call zero gap MIP^*, denoted by MIP^*_0, where there is no promise gap between the verifier's acceptance probabilities in the YES and NO cases. We prove that MIP^*_0 extends beyond the first level of the arithmetical hierarchy (which includes RE and its complement coRE), and in fact is equal to Π_2^0, the class of languages that can be decided by quantified formulas of the form ∀ y ∃ z R(x,y,z). Combined with the previously known result that MIP^co_0 (the commuting operator variant of MIP^*_0) is equal to coRE, our result further highlights the fascinating connection between various models of quantum multiprover interactive proofs and different classes in computability theory.
READ FULL TEXT