Abstract

In quantum information, nonlocal games are particularly useful for differentiating classical, quantum, and non-signalling correlations. In this talk, we present a generalization of the graph isomorphism game, namely the “vertex distance game,” defined with a parameter D∈ℕ. We characterize its perfect strategies, both in the classical, quantum and non-signalling sense, and we connect this notion with a refinement of fractional isomorphism of graphs, namely D-fractional isomorphisms. Surprisingly, we observe that non-signalling strategies provide a finer distinction for this game than classical and quantum strategies since the parameter D is visible only in the non-signalling setting. Finally, we give connections of this game with communication complexity by generating a PR box from a perfect non-signalling strategy. This is a joint work with Moritz Weber [https://arxiv.org/pdf/2406.02199].