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

Estimating quantum chromatic numbers

Vern I. Paulsen, Simone Severini B, Dan Stahlke +2 more

arXiv:1407.6918Journal of Functional AnalysisFeb 2, 201687 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

The exact quantum chromatic number of Hadamard graphs

Meenakshi McNamara

We compute the exact value of the quantum chromatic numbers of Hadamard graphs of order $n=2^N$ for $N$ a multiple of $4$ using the upper bound derived by Avis, Hasegawa, Kikuchi, and Sasaki, as well as an application of the Hoffman-like lower bound of Elphick and Wocjan that was generalized by Ganesan for quantum graphs. As opposed to prior computations for the lower bound, our approach uses Ito's results on conjugacy class graphs allowing us to also find bounds on the quantum chromatic numbers of products of Hadamard graphs. In particular, we also compute the exact quantum chromatic number of the categorical product of Hadamard graphs.We compute the exact value of the quantum chromatic numbers of Hadamard graphs of order $n=2^N$ for $N$ a multiple of $4$ using the upper bound derived by Avis, Hasegawa, Kikuchi, and Sasaki, as well as an application of the Hoffman-like lower bound of Elphick and Wocjan that was generalized by Ganesan for quantum graphs. As opposed to prior computations for the lower bound, our approach uses Ito's results on conjugacy class graphs allowing us to also find bounds on the quantum chromatic numbers of products of Hadamard graphs. In particular, we also compute the exact quantum chromatic number of the categorical product of Hadamard graphs.

arXiv:2410.00042Sep 27, 20240 citations

A counterexample to the quantum Hedetniemi conjecture

Julius A. Zeiss

Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs $G,H$ with $χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).$ The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital $C^*$ -algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and $C^*$ -algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs $G,H$ with \[ χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).\]The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital $C^*$-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and $C^*$-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.

math.COCross-listedarXiv:2609.20690Sep 18, 20260 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.

We compute the exact value of the quantum chromatic numbers of Hadamard graphs of order

n=2^N

for

N

a multiple of

4

using the upper bound derived by Avis, Hasegawa, Kikuchi, and Sasaki, as well as an application of the Hoffman-like lower bound of Elphick and Wocjan that was generalized by Ganesan for quantum graphs. As opposed to prior computations for the lower bound, our approach uses Ito's results on conjugacy class graphs allowing us to also find bounds on the quantum chromatic numbers of products of Hadamard graphs. In particular, we also compute the exact quantum chromatic number of the categorical product of Hadamard graphs.

G,H

with

χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).

The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital

C^*

-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and

C^*

-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.