论文标题
关于零间隙mip*的复杂性*
On the complexity of zero gap MIP*
论文作者
论文摘要
类$ \ mathsf {mip}^*$是通过量子纠缠掠夺者来决定的一组语言。最近由JI，Natarajan，Vidick，Wright和Yuen显示出$ \ Mathsf {Mip}^*$等于$ \ Mathsf {Re} $，这是一组递归枚举的语言。特别是这表明，近似非本地游戏$ g $的量子值的复杂性等于停止问题的复杂性。 在本文中，我们研究了确定非本地游戏$ g $的量子价值是否正好为$ 1 $的复杂性。这个问题对应于一个复杂性类，我们称零差距$ \ mathsf {mip}^*$，由$ \ mathsf {mip}^*_ 0 $表示，其中验证者在YES和否情况下验证者的接受概率之间没有保证差距。 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 $Π_2^0$, the class of languages that can be decided by quantified formulas of the form $\forall y \, \exists z \，r（x，y，z）$。 结合先前已知的结果，即$ \ MATHSF {MIP}^{CO} _0 $（$ \ Mathsf {Mip}^*_ 0 $）的通勤操作员变体等于$ \ Mathsf {coref {coref {core} $，我们的结果进一步强调了量子倍增的各种模型之间的迷人连接，并在量子倍增互动的互动互动中进行了不同，并具有不同的类别。
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 $Π_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.
