Deterministic quantum non-locality and graph colorings (Q387022)

This paper is based on the ``quantum pseudo-telepathy'' phenomenon that occurs in quantum game theory. Even though important features of quantum computation frequently come into play (such as ``quantum non-locality'', ``entanglement'', ``EPR pair of photons''), all the theoretical framework used in the paper is classical and quantum computational algorithms are not involved. The main goal of the paper is to show how pseudo-telepathy games could be modeled as a graph-coloring problem. In Sections 2 and 3, the authors consider the particular case of the game by Brassard, Cleve, and Tapp providing useful definitions to show the correspondence between the two different strategies. They prove theorems and corollaries which rigorously formalize this correspondence. In Section 4 the authors provide interesting upper and lower bound conditions. The paper is a game-theory work. The aim is clear, theorems and proofs are well showed but an empirical application could provide a further motivation to the paper.