Algorithms, Bounds, and Strategies for Entangled XOR Games
share
We study the complexity of computing the commuting-operator value ω^* of entangled XOR games with any number of players. We introduce necessary and sufficient criteria for an XOR game to have ω^* = 1, and use these criteria to derive the following results: 1. An algorithm for symmetric games that decides in polynomial time whether ω^* = 1 or ω^* < 1, a task that was not previously known to be decidable, together with a simple tensor-product strategy that achieves value 1 in the former case. The only previous candidate algorithm for this problem was the Navascués-Pironio-Acín (also known as noncommutative Sum of Squares or ncSoS) hierarchy, but no convergence bounds were known. 2. A family of games with three players and with ω^* < 1, where it takes doubly exponential time for the ncSoS algorithm to witness this (in contrast with our algorithm which runs in polynomial time). 3. A family of games achieving a bias difference 2(ω^* - ω) arbitrarily close to the maximum possible value of 1 (and as a consequence, achieving an unbounded bias ratio), answering an open question of Briët and Vidick. 4. Existence of an unsatisfiable phase for random (non-symmetric) XOR games: that is, we show that there exists a constant C_k^unsat depending only on the number k of players, such that a random k-XOR game over an alphabet of size n has ω^* < 1 with high probability when the number of clauses is above C_k^unsat n. 5. A lower bound of Ω(n (n)/(n)) on the number of levels in the ncSoS hierarchy required to detect unsatisfiability for most random 3-XOR games. This is in contrast with the classical case where the n-th level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.
READ FULL TEXT