The quantum-to-classical graph homomorphism game

Abstract

Motivated by non-local games and quantum coloring problems, we introduce a graph homomorphism game between quantum graphs and classical graphs. This game is naturally cast as a "quantum-classical game"--that is, a non-local game of two players involving quantum questions and classical answers. This game generalizes the graph homomorphism game between classical graphs. We show that winning strategies in the various quantum models for the game is an analogue of the notion of non-commutative graph homomorphisms due to D. Stahlke [44]. Moreover, we present a game algebra in this context that generalizes the game algebra for graph homomorphisms given by J.W. Helton, K. Meyer, V.I. Paulsen and M. Satriano [22]. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the $4$-coloring game for a quantum graph is always non-trivial, extending a result of [22].

arXiv commentv2: fixed errors in proofs of the old Theorem 4.7 and 5.6; removed Lemma 4.8

References in corpus (20)

• All Teleportation and Dense Coding Schemes
• Connes' embedding problem and Tsirelson's problem
• Tsirelson's problem and Kirchberg's conjecture
• Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
• Estimating quantum chromatic numbers
• A compositional approach to quantum functions
• A synchronous game for binary constraint systems
• Bigalois extensions and the graph isomorphism game
• Tsirelson's Problem
• Unconditional separation of finite and infinite-dimensional quantum correlations
• Unitary Correlation Sets
• Algebras, Synchronous Games and Chromatic Numbers of Graphs
• Quantum source-channel coding and non-commutative graph theory
• Perfect Embezzlement of Entanglement
• On zero-error communication via quantum channels in the presence of noiseless feedback
• Quantum channels arising from abstract harmonic analysis
• Quantum no-signalling correlations and non-local games
• Connes' Embedding Problem and Winning Strategies for Quantum XOR Games
• Chromatic numbers and a Lovász type inequality for non-commutative graphs
• Geometry of the set of synchronous quantum correlations

Cited by in corpus (9)

• Quantum no-signalling correlations and non-local games
• Quantum teleportation in the commuting operator framework
• Entanglement-symmetries of covariant channels
• A category of quantum posets
• Quantum graphs, subfactors and tensor categories I
• Repeated temperature measurements in quantum thermodynamics
• Algebraic connectedness and bipartiteness of quantum graphs
• Quantum Suplattices
• Weighted theta functions for non-commutative graphs