Anand Natarajan

Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA

2018

We show that given an explicit description of a multiplayer game, with a classical verifier and a constant number of players, it is QMA-hard, under randomized reductions, to distinguish between the cases when the players …

Quantum soundness of the classical low individual degree test

2020 · arXiv (Cornell University)

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 …