A Caltech Library Service

Quantum soundness of the classical low individual degree test

Ji, Zhengfeng and Natarajan, Anand and Vidick, Thomas and Wright, John and Yuen, Henry (2020) Quantum soundness of the classical low individual degree test. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as MIP = 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 MIP^*. The culmination of this line of work is the result MIP^* = RE [arXiv:2001.04383]. One of the key ingredients in the first reported proof of MIP^* = 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 MIP^* that relied on [arXiv:1302.1242], including MIP^* = RE.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Ji, Zhengfeng0000-0002-7659-3178
Natarajan, Anand0000-0003-3648-3844
Vidick, Thomas0000-0002-6405-365X
Additional Information:We thank Lewis Bowen for pointing out typos and a few minor errors in a previous version. We also thank Madhu Sudan for help with references on the classical low individual degree test.
Record Number:CaltechAUTHORS:20211004-222652076
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:111196
Deposited By: George Porter
Deposited On:04 Oct 2021 23:12
Last Modified:04 Oct 2021 23:12

Repository Staff Only: item control page