Quantum Coloring of Quantum Graphs

Abstract

Quantum graphs are an operator space generalization of classical graphs that have appeared in different branches of mathematics including operator systems theory, non-commutative topology and quantum information theory. In this work, we develop a notion of quantum coloring for quantum graphs using a non-local game with quantum inputs & classical outputs that generalizes the coloring game for classical graphs.

Using this game, we define chromatic numbers for quantum graphs in the various (quantum) models and show that they are a analogue of D.Stahlke’s [53] entanglement assisted chromatic numbers and that the classical model is equivalent to Kim & Mehta’s [37] strong chromatic numbers for non-commutative graphs. We demonstrate explicit quantum colorings of all quantum complete graphs and prove that every quantum graph has a finite quantum chromatic number (but not necessarily classical chromatic number). We also show that every quantum graph is 4-colorable in the algebraic model.

Further, we obtain five lower bounds for the classical and quantum chromatic number of quantum graphs using the spectrum of the quantum adjacency operator. These bounds are achieved by applying a combinatorial characterization of quantum graph coloring obtained from the winning strategies of the quantum-to-classical nonlocal coloring game. We generalize all the spectral estimates of Elphick & Wocjan [19] to the quantum graph setting and in particular, prove a quantum generalization of the Hoffman’s bound. We also demonstrate the tightness of our bounds in the case of quantum complete graphs.