Hamoon Mousavi

The class MIP^* is the set of languages that are decidable by a multiprover interactive proof 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 showed that the complexity of approximating the quantum value of a non-local game G is, in general, 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 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 PI^0_2, the class of languages that can be decided by quantified formulas of the form for all y, there exists 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.