摘要：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â,^*, where there is no promise gap between the verifierâs acceptance probabilities in the YES and NO cases. We prove that MIPâ,^* extends beyond the first level of the arithmetical hierarchy (which includes RE and its complement coRE), and in fact is equal to Î â,,â°, the class of languages that can be decided by quantified formulas of the form â^ y â^f z R(x,y,z). Combined with the previously known result that MIPâ,^{co} (the commuting operator variant of MIPâ,^*) 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.
关键词：Quantum Complexity; Multiprover Interactive Proofs; Computability Theory
