Nonlocal games, compression theorems, and the arithmetical hierarchy

Abstract

We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical formulas defining them. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that deciding whether the (finite-dimensional) quantum value of a nonlocal game is 1 or at most 1/2 is complete for the class Σ1 (i.e., ). A result of Slofstra implies that deciding whether the commuting operator value of a nonlocal game is equal to 1 is complete for the class Π1 (i.e., coRE).