Can I read Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy on EtoBox?

Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy by Hamoon Mousavi; Seyed Sajjad Nezhadi; Henry Yuen is a scholarly article available to read on EtoBox.

What is Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy about?

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., RE). 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).We prove that deciding whether the quantum value of a twoplayer nonlocal game is exactly equal to 1 is complete for Π 2 ; this class is in the second level of the arithmetical hierarchy and corresponds to formulas of the form "∀x ∃y φ (x, y)". This shows that exactly computing the quantum value is strictly harder than approximating it, and also strictly harder than computing the commuting operator value (either exactly or approximately).We explain how results about the complexity of nonlocal games all follow in a unified manner from a technique known as compression. At the core of our Π 2 -completeness result is a new "gapless" c

Author

Hamoon Mousavi; Seyed Sajjad Nezhadi; Henry Yuen

Publisher

ACM

Published

2022

Language

EN