arXiv:2412.09904

Quantum chromatic numbers of some graphs in Hamming schemes

Xiwang Cao, Keqin Feng, Ying-Ying Tan

Published Dec 13, 2024• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2412.09904

Related papers

The exact quantum chromatic number of Hadamard graphs

Meenakshi McNamara

arXiv:2410.00042Sep 27, 20240 citations

Quantum Chromatic Number of Subgraphs of Orthogonality Graphs and the Distance-2 Hamming Graph

Tao Luo, Yu Ning, Xiande Zhang

math.COCross-listedarXiv:2512.01195The Electronic Journal of CombinatoricsDec 2, 20250 citations

On the Quantum Chromatic Numbers of Small Graphs

Olivier Lalonde

arXiv:2311.08194The Electronic Journal of CombinatoricsFeb 14, 20251 citation

Quantum independence and chromatic numbers

Godsil, Chris, Sobchuk, Mariia

arXiv:2401.16518Jan 29, 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

arXiv:2412.09904

Quantum chromatic numbers of some graphs in Hamming schemes

Xiwang Cao, Keqin Feng, Ying-Ying Tan

Published Dec 13, 2024• 0 citations

arXiv HTML PDF

Abstract

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.

DOI: 10.48550/arxiv.2412.09904

Related papers

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

Quantum Chromatic Number of Subgraphs of Orthogonality Graphs and the Distance-2 Hamming Graph

Tao Luo, Yu Ning, Xiande Zhang

The determination of the quantum chromatic number of graphs has attracted considerable attention recently. However, there are few families of graphs whose quantum chromatic numbers are determined. A notable exception is the family of orthogonality graphs, whose quantum chromatic numbers are fully determined. In this paper, we extend these results by determining the exact quantum chromatic number of several subgraphs of the orthogonality graphs. Using the technique of combinatorial designs, we also determine the quantum chromatic number of the distance-2 Hamming graph, whose edges consist of binary vectors of Hamming distance 2, for infinitely many length.The determination of the quantum chromatic number of graphs has attracted considerable attention recently. However, there are few families of graphs whose quantum chromatic numbers are determined. A notable exception is the family of orthogonality graphs, whose quantum chromatic numbers are fully determined. In this paper, we extend these results by determining the exact quantum chromatic number of several subgraphs of the orthogonality graphs. Using the technique of combinatorial designs, we also determine the quantum chromatic number of the distance-2 Hamming graph, whose edges consist of binary vectors of Hamming distance 2, for infinitely many length.

math.COCross-listedarXiv:2512.01195The Electronic Journal of CombinatoricsDec 2, 20250 citations

On the Quantum Chromatic Numbers of Small Graphs

Olivier Lalonde

We make two contributions pertaining to the study of the quantum chromatic numbers of small graphs. Firstly, in an elegant paper, Mančinska and Roberson [Baltic Journal on Modern Computing, 4(4), 846-859, 2016] gave an example of a graph $G_{14}$ on 14 vertices with quantum chromatic number 4 and classical chromatic number 5, and conjectured that this is the smallest graph exhibiting a separation between the two parameters. We describe a computer-assisted proof of this conjecture, thereby resolving a longstanding open problem in quantum graph theory. Our second contribution pertains to the study of the rank- $r$ quantum chromatic numbers. While it can now be shown that for every $r$ , $\chi_q$ and $\chi^{(r)}_q$ are distinct, few small examples of separations between these parameters are known. We give the smallest known example of such a separation in the form of a graph $G_{21}$ on 21 vertices with $\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4$ and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph $G_{msg}$ on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies $\chi_q(G_{msg}) = 3$ and $\chi^{(1)}_q(G_{msg}) = 4$ . In addition, $G_{21}$ provides the first provable separation between the parameters $\chi^{(1)}_q$ and $\chi^{(2)}_q$ . We believe that our techniques for constructing $G_{21}$ and lower bounding its orthogonal rank could be of independent interest.We make two contributions pertaining to the study of the quantum chromatic numbers of small graphs. Firstly, in an elegant paper, Mančinska and Roberson [Baltic Journal on Modern Computing, 4(4), 846-859, 2016] gave an example of a graph $G_{14}$ on 14 vertices with quantum chromatic number 4 and classical chromatic number 5, and conjectured that this is the smallest graph exhibiting a separation between the two parameters. We describe a computer-assisted proof of this conjecture, thereby resolving a longstanding open problem in quantum graph theory. Our second contribution pertains to the study of the rank-$r$ quantum chromatic numbers. While it can now be shown that for every $r$, $\chi_q$ and $\chi^{(r)}_q$ are distinct, few small examples of separations between these parameters are known. We give the smallest known example of such a separation in the form of a graph $G_{21}$ on 21 vertices with $\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4$ and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph $G_{msg}$ on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies $\chi_q(G_{msg}) = 3$ and $\chi^{(1)}_q(G_{msg}) = 4$. In addition, $G_{21}$ provides the first provable separation between the parameters $\chi^{(1)}_q$ and $\chi^{(2)}_q$. We believe that our techniques for constructing $G_{21}$ and lower bounding its orthogonal rank could be of independent interest.

arXiv:2311.08194The Electronic Journal of CombinatoricsFeb 14, 20251 citation

Quantum independence and chromatic numbers

Godsil, Chris, Sobchuk, Mariia

We construct a new graph on 120 vertices whose quantum and classical independence numbers are different. At the same time, we construct an infinite family of graphs whose quantum chromatic numbers are smaller than the classical chromatic numbers. Furthermore, we discover the relation to Kochen-Specker sets that characterizes quantum cocliques that are strictly bigger than classical ones. Finally, we prove that for graphs with independence number is two, quantum and classical independence numbers coincide.We construct a new graph on 120 vertices whose quantum and classical independence numbers are different. At the same time, we construct an infinite family of graphs whose quantum chromatic numbers are smaller than the classical chromatic numbers. Furthermore, we discover the relation to Kochen-Specker sets that characterizes quantum cocliques that are strictly bigger than classical ones. Finally, we prove that for graphs with independence number is two, quantum and classical independence numbers coincide.

arXiv:2401.16518Jan 29, 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

H_n

with

2^n

vertices and

n

a multiple of

4

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_{14}

on 14 vertices with quantum chromatic number 4 and classical chromatic number 5, and conjectured that this is the smallest graph exhibiting a separation between the two parameters. We describe a computer-assisted proof of this conjecture, thereby resolving a longstanding open problem in quantum graph theory. Our second contribution pertains to the study of the rank-

r

quantum chromatic numbers. While it can now be shown that for every

r

\chi_q

and

\chi^{(r)}_q

are distinct, few small examples of separations between these parameters are known. We give the smallest known example of such a separation in the form of a graph

G_{21}

on 21 vertices with

\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4

and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph

G_{msg}

on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies

\chi_q(G_{msg}) = 3

and

\chi^{(1)}_q(G_{msg}) = 4

. In addition,

G_{21}

provides the first provable separation between the parameters

\chi^{(1)}_q

and

\chi^{(2)}_q

. We believe that our techniques for constructing

G_{21}

and lower bounding its orthogonal rank could be of independent interest.

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.