Quantum soundness of the classical low individual degree test

arXiv2009.12982MaRDI QIDQ6349986FDOQ6349986

Henry C. Yuen, Thomas Vidick, John R. Wright, Zhengfeng Ji, Anand Natarajan

Publication date: 27 September 2020

Abstract: Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as $mathsfMIP=mathsfNEXP$ [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}^{*}=mathsfRE$ [arXiv:2001.04383]. One of the key ingredients in the first reported proof of $mathsf{MIP}^{*}=mathsfRE$ 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}^{*}=mathsfRE$.

This page was built for publication: Quantum soundness of the classical low individual degree test

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6349986)