Transitive Nonlocal Games

Abstract

We study a class of nonlocal games, called transitive games, for which the set of perfect strategies forms a semigroup. We establish several interesting correspondences of bisynchronous transitive games with the theory of compact quantum groups. In particular, we associate a quantum permutation group with each bisynchronous transitive game and vice versa. We prove that the existence of a C*-strategy, the existence of a quantum commuting strategy, and the existence of a classical strategy are all equivalent for bisynchronous transitive games. We then use some of these correspondences to establish necessary and sufficient conditions for some classes of correlations, that arise as perfect strategies of transitive games, to be nonlocal.

References in corpus (10)

• Quantum Symmetry Groups of Finite Spaces
• Co-Amenability of compact quantum groups
• Estimating quantum chromatic numbers
• Graph Homomorphisms for Quantum Players
• Quantum families of maps and quantum semigroups on finite quantum spaces
• Tsirelson's problem and an embedding theorem for groups arising from non-local games
• A compositional approach to quantum functions
• Algebras, Synchronous Games and Chromatic Numbers of Graphs
• Perfect strategies for non-signalling games
• Quantum Semigroups from Synchronous Games