In this talk I will consider the complexity of the problem of determining, given a nonlocal XOR game with k = 3 players, whether there exists an entangled strategy for the game using commuting operators that succeeds with probability 1. Our first result is a polynomial-time algorithm to solve this problem for any k; previously, this problem was not known to be decidable, and indeed, it was shown recently by Slofstra that the same question for a different class of games is undecidable. Our second result is a characterization of random symmetric XOR games: we show that there exists a constant C_k depending only on k, such that a random symmetric k-player XOR game with question alphabet size n has no perfect entangled strategy with high probability when the number of clauses is above C_k *n. Moreover, for random (not necessarily symmetric) games in the regime where no perfect entangled strategy exists, we show a lower bound on the number of levels in the NPA (Navascues-Pironio-Acin) hierarchy of semidefinite programs needed to witness this fact. Joint work with Adam Bene Watts and Aram Harrow (both at MIT).
De Anthony Leverrier
De Zbigniew Puchała
De Benoit Collins
De Satya Majumdar
De Motohisa Fukuda
De Nilanjana Datta
De Daniel Stilck Franca
De Radosław Adamczak
De Madalin Guta
De Antonio Acín
De Ashley Montanaro
De Ping Zhong
De James Mingo
De Camille Male
De Clément Delcamp
De Clément Delcamp
De Giuseppe Savaré
