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).
By Anthony Leverrier
By Zbigniew Puchała
By Benoit Collins
By Satya Majumdar
By Motohisa Fukuda
By Anand Natarajan
By Nilanjana Datta
By Daniel Stilck Franca
By Ke Li
By Radosław Adamczak
By Madalin Guta
By Antonio Acín
By Ashley Montanaro
By Ping Zhong
By James Mingo
By Camille Male
By Clément Delcamp
By Clément Delcamp
By Claudio Dappiaggi
