Graph Homomorphisms for Quantum Players

Abstract

A homomorphism from a graph $X$ to a graph $Y$ is an adjacency preserving mapping $f:V(X)\to V(Y)$. We consider a nonlocal game in which Alice and Bob are trying to convince a verifier with certainty that a graph $X$ admits a homomorphism to $Y$. This is a generalization of the well-studied graph coloring game. Via systematic study of quantum homomorphisms we prove new results for graph coloring. Most importantly, we show that the Lovász theta number of the complement lower bounds the quantum chromatic number, which itself is not known to be computable. We also show that some of our newly introduced graph parameters, namely quantum independence and clique numbers, can differ from their classical counterparts while others, namely quantum odd girth, cannot. Finally, we show that quantum homomorphisms closely relate to zero-error channel capacity. In particular, we use quantum homomorphisms to construct graphs for which entanglement-assistance increases their one-shot zero-error capacity.

References in corpus (3)

• A Generalization of Kochen-Specker Sets Relates Quantum Coloring to Entanglement-Assisted Channel Capacity
• Violating the Shannon capacity of metric graphs with entanglement
• Conic Formulations of Graph Homomorphisms

Cited by in corpus (28)

• The contextual fraction as a measure of contextuality
• A compositional approach to quantum functions
• Converting contextuality into nonlocality
• Quantum Bilinear Optimization
• Perfect strategies for non-signalling games
• Linear conic formulations for two-party correlations and values of nonlocal games
• Quantum sets
• Graph-theoretic approach to Bell experiments with low detection efficiency
• Non-closure of the set of quantum correlations via graphs
• Thinness of product graphs
• Deciding the existence of perfect entangled strategies for nonlocal games
• State-independent quantum contextuality with projectors of nonunit rank
• A unified construction of semiring-homomorphic graph invariants
• Quantum Semigroups from Synchronous Games
• Nonlocal games, synchronous correlations, and Bell inequalities
• A natural deduction system for orthomodular logic
• A category of quantum posets
• The Haemers bound of noncommutative graphs
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Discrete quantum structures
• Counterexamples in self-testing
• A Spectral Lower Bound on Chromatic Numbers using $p$-Energy
• A family of non-Cayley cores based on vertex-transitive or strongly regular self-complementary graphs
• Effectus of Quantum Probability on Relational Structures
• Morphisms in categories of nonlocal games
• Quantum advantage in zero-error function computation with side information
• Transitive Nonlocal Games
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization