Quantum soundness of the classical low individual degree test
| Title: | Quantum soundness of the classical low individual degree test |
|---|---|
| Authors: | Ji, Zhengfeng, Natarajan, Anand, Vidick, Thomas, Wright, John, Yuen, Henry |
| Publication Year: | 2020 |
| Collection: | Computer Science Mathematics Quantum Physics |
| Subject Terms: | Quantum Physics, Computer Science - Computational Complexity, Mathematics - Probability |
| More Details: | 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}$. |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2009.12982 |
| Accession Number: | edsarx.2009.12982 |
| Database: | arXiv |
| Description not available. |