Spectral lower bounds for the quantum chromatic number of a graph

Abstract

The quantum chromatic number, $χ_q(G)$, of a graph $G$ was originally defined as the minimal number of colors necessary in a quantum protocol in which two provers that cannot communicate with each other but share an entangled state can convince an interrogator with certainty that they have a coloring of the graph. We use an equivalent purely combinatorial definition of $χ_q(G)$ to prove that many spectral lower bounds for the chromatic number, $χ(G)$, are also lower bounds for $χ_q(G)$. This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.

Added funding info