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.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.

arXiv:1805.08334May 22, 20181 citation

Spectral fluctuations of quantum graphs

Z. Pluhař, Hans A. Weidenmüller

AIP conference proceedingsJan 1, 20140 citations

Klasyczne i kwantowe grafy Knesera

Igor Chełstowski

We present a construction of quantum Kneser graphs, which yields classical Kneser graphs in the commutative case.We also generalize this construction to obtain quantum versions of generalized Kneser graphs, such as Johnson graphs.We discuss several basic properties of the constructed quantum graphs, such as their reflexivity and regularity.Then, we investigate their quantum chromatic numbers and establish upper bounds on them by constructing explicit colorings.We also investigate spectral lower bounds on quantum chromatic numbers for several examples and formulate a conjecture about their asymptotic behavior.Lastly, we present an alternate approach to quantization of Kneser graphs and a few results obtained for the quantum Mycielski construction.We present a construction of quantum Kneser graphs, which yields classical Kneser graphs in the commutative case.We also generalize this construction to obtain quantum versions of generalized Kneser graphs, such as Johnson graphs.We discuss several basic properties of the constructed quantum graphs, such as their reflexivity and regularity.Then, we investigate their quantum chromatic numbers and establish upper bounds on them by constructing explicit colorings.We also investigate spectral lower bounds on quantum chromatic numbers for several examples and formulate a conjecture about their asymptotic behavior.Lastly, we present an alternate approach to quantization of Kneser graphs and a few results obtained for the quantum Mycielski construction.

Jan 1, 20260 citations

On the properties of simple quantum graphs

Pavel Hejčík

Jan 1, 20080 citations

Quantum graphs special section

Waves in Random MediaJan 1, 20040 citations

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.