Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The Quarterly Journal of Mathematics

QUANTUM CHROMATIC NUMBERS VIA OPERATOR SYSTEMS

Vern I. Paulsen, Ivan G. Todorov

Published Mar 3, 2015• 41 citations
Publisher

Abstract

We define several new types of quantum chromatic numbers of a graph and characterize them in terms of operator system tensor products. We establish inequalities between these chromatic numbers and other parameters of graphs studied in the literature and exhibit a link between them and non-signalling correlation boxes.
DOI
10.1093/qmath/hav004

Related papers

Quantum chromatic numbers via operator systems

Vern I. Paulsen, Ivan G. Todorov

We define several new types of quantum chromatic numbers of a graph and characterise them in terms of operator system tensor products. We establish inequalities between these chromatic numbers and other parameters of graphs studied in the literature and exhibit a link between them and non-signalling correlation boxes.

arXiv:1311.6850•Nov 26, 2013•6 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.

arXiv:2408.11911•Aug 21, 2024•0 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 Physics•Dec 1, 2025•0 citations

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.

arXiv:2412.09904•Dec 13, 2024•0 citations

Operator systems from discrete groups

Douglas Farenick, Ali S. Kavruk, Vern I. Paulsen +1 more

We formulate a general framework for the study of operator systems arising from discrete groups. We study in detail the operator system of the free group on $n$ generators, as well as the operator systems of the free products of finitely many copies of the two-element group $\mathbb Z_2$. We examine various tensor products of group operator systems, including the minimal, the maximal, and the commuting tensor products. We introduce a new tensor product in the category of operator systems and formulate necessary and sufficient conditions for its equality to the commuting tensor product in the case of group operator systems. We express various sets of quantum correlations studied in the theoretical physics literature in terms of different tensor products of operator systems of discrete groups. We thus recover earlier results of Tsirelson and formulate a new approach for the study of quantum correlation boxes.

arXiv:1209.1152•Sep 6, 2012•4 citations

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.

arXiv:2401.16518•Jan 29, 2024•0 citations
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 bbb-fold chromatic number for quantum 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 HnH_nHn​ with 2n2^n2n vertices and nnn a multiple of 444. 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.
We formulate a general framework for the study of operator systems arising from discrete groups. We study in detail the operator system of the free group on nnn generators, as well as the operator systems of the free products of finitely many copies of the two-element group Z2\mathbb Z_2Z2​. We examine various tensor products of group operator systems, including the minimal, the maximal, and the commuting tensor products. We introduce a new tensor product in the category of operator systems and formulate necessary and sufficient conditions for its equality to the commuting tensor product in the case of group operator systems. We express various sets of quantum correlations studied in the theoretical physics literature in terms of different tensor products of operator systems of discrete groups. We thus recover earlier results of Tsirelson and formulate a new approach for the study of quantum correlation boxes.
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.