The Mermin-Peres magic square game is a cooperative two-player nonlocal game in which shared quantum entanglement allows the players to win with certainty, while players limited to classical operations cannot do so, a phenomenon dubbed "quantum pseudo-telepathy". The game has a referee separately ask each player to color a subset of a 3x3 grid. The referee checks that their colorings satisfy certain parity constraints that can't all be simultaneously realized. We define a generalization of these games to be played on an arbitrary arrangement of intersecting sets of elements. We characterize exactly which of these games exhibit quantum pseudo-telepathy, and give quantum winning strategies for those that do. In doing so, we show that it suffices for the players to share three Bell pairs of entanglement even for games on arbitrarily large arrangements. Moreover, it suffices for Alice and Bob to use measurements from the three-qubit Pauli group. The proof technique uses a novel connection of Mermin-style games to graph planarity.
We establish the first hardness results for the problem of computing the value of one-round games played by a referee and a team of players who can share quantum entanglement. In particular, we show that it is NP-hard to approximate within an inverse polynomial the value of a one-round game with (i) quantum referee and two entangled players or (ii) classical referee and three entangled players. Previously it was not even known if computing the value exactly is NP-hard. We also describe a mathematical conjecture, which, if true, would imply hardness of approximation to within a constant.We start our proof by describing two ways to modify classical multi-player games to make them resistant to entangled players. We then show that a strategy for the modified game that uses entanglement can be "rounded'' to one that does not. The results then follow from classical inapproximability bounds. Our work implies that, unless P = NP, the values of entangled-player games cannot be computed by semidefinite programs that are polynomial in the size of the referee's system, a method that has been successful for more restricted quantum games.
We look at Bell inequalities from the lens of information structures in stochastic teams. We consider the usual Clauser-Horne-Shimony-Holt (CHSH) game and a dynamic variant of the same to study how various classes of strategies, classical, projective and quantum, behave under team theoretic solution concepts. We endow players with a fixed quantum state that we take as the Bell state, and allow variation of the measurement strategies. In the static game, projective strategies (where each player performs projective measurements) are team optimal for all parameter values and are closed under best response. In the dynamic game these properties fail: projective strategies may be strictly outperformed by classical ones, best responses to projective strategies need not be projective, and, beyond a sharp threshold on the channel noise, team optimal projective strategies cease to be person-by-person optimal, even though person-by-person optimal projective pairs always exist. These results shed light on the delicate interplay of information structure in quantum strategies and the fragility, under a change of information structure, of structural properties that are taken for granted in the static setting.