  The class $\mathsf{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 $\mathsf{MIP}^*$ is equal to
$\mathsf{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 $\mathsf{MIP}^*$, denoted by
$\mathsf{MIP}^*_0$, where there is no promise gap between the verifier's
acceptance probabilities in the YES and NO cases. We prove that
$\mathsf{MIP}^*_0$ extends beyond the first level of the arithmetical hierarchy
(which includes $\mathsf{RE}$ and its complement $\mathsf{coRE}$), and in fact
is equal to $\Pi_2^0$, the class of languages that can be decided by quantified
formulas of the form $\forall y \, \exists z \, R(x,y,z)$.
  Combined with the previously known result that $\mathsf{MIP}^{co}_0$ (the
commuting operator variant of $\mathsf{MIP}^*_0$) is equal to $\mathsf{coRE}$,
our result further highlights the fascinating connection between various models
of quantum multiprover interactive proofs and different classes in
computability theory.
