Universality of Graph Homomorphism Games and the Quantum Coloring Problem

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We show that quantum graph parameters for finite, simple, undirected graphs encode winning strategies for all possible synchronous non-local games. Given a synchronous game G=(I,O,λ) with |I|=n and |O|=k, we demonstrate what we call a weak ∗-equivalence between G and a 3-coloring game on a graph with at most 3+n+9n(k-2)+6|λ-1({0})| vertices, strengthening and simplifying work implied by Ji [16] for winning quantum strategies for synchronous non-local games. As an application, we obtain a quantum version of Lovász’s reduction [21] of the k-coloring problem for a graph G with n vertices and m edges to the 3-coloring problem for a graph with 3+n+9n(k-2)+6mk vertices. Moreover, winning strategies for a synchronous game G can be transformed into winning strategies for an associated graph coloring game, where the strategies exhibit perfect zero knowledge for an honest verifier. We also show that, for “graph of the game” X(G) associated with G from Atserias et al. [1], the independence number game Hom(K|I|,X(G)¯) is hereditarily ∗-equivalent to G, so that the possibility of winning strategies is the same in both games for all models, except the game algebra. Thus, the quantum versions of the chromatic number, independence number and clique number encode winning strategies for all synchronous games in all quantum models.

Original languageEnglish (US)
Pages (from-to)4321-4356
Number of pages36
JournalAnnales Henri Poincare
Volume25
Issue number10
DOIs
StatePublished - Oct 2024

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Nuclear and High Energy Physics
  • Mathematical Physics

Fingerprint

Dive into the research topics of 'Universality of Graph Homomorphism Games and the Quantum Coloring Problem'. Together they form a unique fingerprint.

Cite this