论文标题
经典低个体学位测试的量子声音
Quantum soundness of the classical low individual degree test
论文作者
论文摘要
低度测试在经典复杂性理论中起着重要作用，在基础结果中充当基本成分，例如$ \ Mathsf {MIP} = \ Mathsf {nexp} $ [BFL91]和PCP Theorem [AS98，Alm+98]。在过去的十年中，针对量子抛弃的声音的这些测试的版本发现，在非本地游戏的研究和复杂性类别〜$ \ mathsf {mip}^*$中增加了应用程序。这项工作的结晶是结果$ \ mathsf {mip}^* = \ mathsf {re} $ [arxiv：2001.04383]。 $ \ mathsf {mip}^* = \ mathsf {re} $的第一个报道证明中的关键成分之一是低度测试的两杆变体，最初证明对[arxiv：1302.1242]中的多个量子摊贩表现出对多个量子摊贩的声音。不幸的是，最近在后一个结果中发现了一个错误，这使[Arxiv：1302.1242]的主要结果无效，并在随后的作品中使用，包括[Arxiv：2001.04383]。我们分析了低度测试的变体称为低个体学位测试。我们的主要结果是，该测试的两个玩家版本是对量子抛弃的声音。这种健全的结果足以重新启用〜$ \ MATHSF {MIP}^* $的几个界限，该界限依赖于[Arxiv：1302.1242]，包括$ \ Mathsf {MIP}^* = \ Mathsf {re} $。
Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as $\mathsf{MIP} = \mathsf{NEXP}$ [BFL91] and the PCP theorem [AS98,ALM+98]. Over the last ten years, versions of these tests which are sound against quantum provers have found increasing applications to the study of nonlocal games and the complexity class~$\mathsf{MIP}^*$. The culmination of this line of work is the result $\mathsf{MIP}^* = \mathsf{RE}$ [arXiv:2001.04383]. One of the key ingredients in the first reported proof of $\mathsf{MIP}^* = \mathsf{RE}$ is a two-prover variant of the low degree test, initially shown to be sound against multiple quantum provers in [arXiv:1302.1242]. Unfortunately a mistake was recently discovered in the latter result, invalidating the main result of [arXiv:1302.1242] as well as its use in subsequent works, including [arXiv:2001.04383]. We analyze a variant of the low degree test called the low individual degree test. Our main result is that the two-player version of this test is sound against quantum provers. This soundness result is sufficient to re-derive several bounds on~$\mathsf{MIP}^*$ that relied on [arXiv:1302.1242], including $\mathsf{MIP}^* = \mathsf{RE}$.
