arXiv:2410.00042

The exact quantum chromatic number of Hadamard graphs

Meenakshi McNamara

Published Sep 27, 2024• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2410.00042

Related papers

Quantum chromatic numbers of some graphs in Hamming schemes

Xiwang Cao, Keqin Feng, Ying-Ying Tan

arXiv:2412.09904Dec 13, 20240 citations

On the exact quantum chromatic number of generalized Johnson graphs

Gaojun Luo, Xiwang Cao, Shitao Li +1 more

arXiv:2609.04677Sep 4, 20260 citations

Quantum chromatic numbers of products of quantum graphs

de Santiago, Rolando, A. Meenakshi McNamara

arXiv:2408.11911Aug 21, 20240 citations

A counterexample to the quantum Hedetniemi conjecture

Julius A. Zeiss

math.COCross-listedarXiv:2609.20690Sep 18, 20260 citations

Quantum chromatic number of products of quantum graphs

Rolando de Santiago, A. Meenakshi McNamara

In this article, we define the Cartesian, Categorical, and Lexicographic, and Strong products of quantum graphs. We provide bounds on the quantum chromatic number of these products in terms of the quantum chromatic number of the factors. To adequately describe bounds on the lexicographic product of quantum graphs, we provide a notion of a quantum b-fold chromatic number for quantum graphs.

Journal of Mathematical PhysicsDec 1, 20250 citations

1 Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number

Giannicola Scarpa, Simone Severini B

Apr 1, 201225 citations

arXiv:2410.00042

The exact quantum chromatic number of Hadamard graphs

Meenakshi McNamara

Published Sep 27, 2024• 0 citations

arXiv HTML PDF

Abstract

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.

DOI: 10.48550/arxiv.2410.00042

Related papers

Quantum chromatic numbers of some graphs in Hamming schemes

Xiwang Cao, Keqin Feng, Ying-Ying Tan

The study of quantum chromatic numbers of graphs is a hot research topic in recent years. However, the infinite family of graphs with known quantum chromatic numbers are rare, as far as we know, the only known such graphs (except for complete graphs, cycles, bipartite graphs and some trivial cases) are the Hadamard graphs $H_n$ with $2^n$ vertices and $n$ a multiple of $4$ . In this paper, we consider the graphs in Hamming schemes, we determined the quantum chromatic numbers of one class of such graphs. Notably, this is the second known family of graphs whose quantum chromatic numbers are explicitly determined except for some cases aforementioned. We also provide some bounds for the quantum chromatic numbers of some other graphs in Hamming schemes. Consequently, we can obtain the quantum chromatic numbers of products of some graphs.The study of quantum chromatic numbers of graphs is a hot research topic in recent years. However, the infinite family of graphs with known quantum chromatic numbers are rare, as far as we know, the only known such graphs (except for complete graphs, cycles, bipartite graphs and some trivial cases) are the Hadamard graphs $H_n$ with $2^n$ vertices and $n$ a multiple of $4$. In this paper, we consider the graphs in Hamming schemes, we determined the quantum chromatic numbers of one class of such graphs. Notably, this is the second known family of graphs whose quantum chromatic numbers are explicitly determined except for some cases aforementioned. We also provide some bounds for the quantum chromatic numbers of some other graphs in Hamming schemes. Consequently, we can obtain the quantum chromatic numbers of products of some graphs.

arXiv:2412.09904Dec 13, 20240 citations

On the exact quantum chromatic number of generalized Johnson graphs

Gaojun Luo, Xiwang Cao, Shitao Li +1 more

The quantum chromatic number is a fundamental parameter in the study of nonlocal games, capturing the extent to which entanglement can improve performance in distributed tasks. In this paper, we investigate the quantum chromatic number of generalized Johnson graphs. By constructing modulus-one orthogonal representations, we obtain general upper bounds on their quantum chromatic numbers. We further analyze the smallest eigenvalue of these graphs. Combining the resulting Hoffman-type lower bounds with the upper bounds obtained from orthogonal representations, we determine the exact quantum chromatic numbers of two infinite families of generalized Johnson graphs. Finally, applying a forbidden-distance theorem for binary codes, we show that the classical chromatic numbers of these families grow exponentially with $n$ , whereas their quantum chromatic numbers grow linearly. These families exhibit an exponential separation between the classical and quantum chromatic numbers.The quantum chromatic number is a fundamental parameter in the study of nonlocal games, capturing the extent to which entanglement can improve performance in distributed tasks. In this paper, we investigate the quantum chromatic number of generalized Johnson graphs. By constructing modulus-one orthogonal representations, we obtain general upper bounds on their quantum chromatic numbers. We further analyze the smallest eigenvalue of these graphs. Combining the resulting Hoffman-type lower bounds with the upper bounds obtained from orthogonal representations, we determine the exact quantum chromatic numbers of two infinite families of generalized Johnson graphs. Finally, applying a forbidden-distance theorem for binary codes, we show that the classical chromatic numbers of these families grow exponentially with $n$, whereas their quantum chromatic numbers grow linearly. These families exhibit an exponential separation between the classical and quantum chromatic numbers.

arXiv:2609.04677Sep 4, 20260 citations

Quantum chromatic numbers of products of quantum graphs

de Santiago, Rolando, A. Meenakshi McNamara

We define the Cartesian, Categorical, and Lexicographic, and Strong products of quantum graphs. We provide bounds on the quantum chromatic number of these products in terms of the quantum chromatic number of the factors. To adequately describe bounds on the lexicographic product of quantum graphs, we provide a notion of a quantum $b$ -fold chromatic number for quantum graphs.We define the Cartesian, Categorical, and Lexicographic, and Strong products of quantum graphs. We provide bounds on the quantum chromatic number of these products in terms of the quantum chromatic number of the factors. To adequately describe bounds on the lexicographic product of quantum graphs, we provide a notion of a quantum $b$-fold chromatic number for quantum graphs.

arXiv:2408.11911Aug 21, 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

Quantum chromatic number of products of quantum graphs

Rolando de Santiago, A. Meenakshi McNamara

Journal of Mathematical PhysicsDec 1, 20250 citations

1 Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number

Giannicola Scarpa, Simone Severini B

The quantum chromatic number of a graph $G$ is sandwiched between its chromatic number and its clique number, which are well known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number $\chi_q^{(1)}(G)$ , which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number $\chi(G)$ and the minimum dimension of orthogonal representations $\xi(G)$ . It is known that $\xi(G) \leq \chi_q^{(1)}(G) \leq \chi(G)$ . We answer three open questions about these relations: we give a necessary and sufficient condition to have $\xi(G) = \chi_q^{(1)}(G)$ , we exhibit a class of graphs such that $\xi(G) < \chi_q^{(1)}(G)$ , and we give a necessary and sufficient condition to have $\chi_q^{(1)}(G) < \chi(G)$ . Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of noncontextuality of physical theories, and more recently in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis, Hasegawa, Kikuchi, and Sasaki on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.The quantum chromatic number of a graph $G$ is sandwiched between its chromatic number and its clique number, which are well known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number $\chi_q^{(1)}(G)$, which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number $\chi(G)$ and the minimum dimension of orthogonal representations $\xi(G)$. It is known that $\xi(G) \leq \chi_q^{(1)}(G) \leq \chi(G)$. We answer three open questions about these relations: we give a necessary and sufficient condition to have $\xi(G) = \chi_q^{(1)}(G)$, we exhibit a class of graphs such that $\xi(G) < \chi_q^{(1)}(G)$, and we give a necessary and sufficient condition to have $\chi_q^{(1)}(G) < \chi(G)$. Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of noncontextuality of physical theories, and more recently in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis, Hasegawa, Kikuchi, and Sasaki on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.

Apr 1, 201225 citations

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

n=2^N

for

N

a multiple of

4

H_n

with

2^n

vertices and

n

a multiple of

4

. In this paper, we consider the graphs in Hamming schemes, we determined the quantum chromatic numbers of one class of such graphs. Notably, this is the second known family of graphs whose quantum chromatic numbers are explicitly determined except for some cases aforementioned. We also provide some bounds for the quantum chromatic numbers of some other graphs in Hamming schemes. Consequently, we can obtain the quantum chromatic numbers of products of some graphs.

n

, whereas their quantum chromatic numbers grow linearly. These families exhibit an exponential separation between the classical and quantum chromatic numbers.

b

-fold chromatic number for quantum 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.

The quantum chromatic number of a graph

G

is sandwiched between its chromatic number and its clique number, which are well known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number

\chi_q^{(1)}(G)

, which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number

\chi(G)

and the minimum dimension of orthogonal representations

\xi(G)

. It is known that

\xi(G) \leq \chi_q^{(1)}(G) \leq \chi(G)

. We answer three open questions about these relations: we give a necessary and sufficient condition to have

\xi(G) = \chi_q^{(1)}(G)

, we exhibit a class of graphs such that

\xi(G) < \chi_q^{(1)}(G)

, and we give a necessary and sufficient condition to have

\chi_q^{(1)}(G) < \chi(G)

. Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of noncontextuality of physical theories, and more recently in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis, Hasegawa, Kikuchi, and Sasaki on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.