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

arXiv:1311.6850

Quantum chromatic numbers via operator systems

Vern I. Paulsen, Ivan G. Todorov

Published Nov 26, 2013• 6 citations
arXivHTMLPDF

Abstract

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.
DOI
10.48550/arxiv.1311.6850

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

The Quarterly Journal of Mathematics•Mar 3, 2015•41 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

On the Quantum Chromatic Number of a Graph

Peter J‎. Cameron, Ashley Montanaro, Michael Newman +2 more

We investigate the notion of quantum chromatic number of a graph, which is the minimal number of colours necessary in a protocol in which two separated provers can convince a referee that they have a colouring of the graph.After discussing this notion from first principles, we go on to establish relations with the clique number and orthogonal representations of the graph. We also prove several general facts about this graph parameter and find large separations between the clique number and the quantum chromatic number by looking at random graphs. Finally, we show that there can be no separation between classical and quantum chromatic number if the latter is $2$, nor if it is $3$ in a restricted quantum model; on the other hand, we exhibit a graph on $18$ vertices and $44$ edges with chromatic number $5$ and quantum chromatic number $4$.

The Electronic Journal of Combinatorics•Nov 28, 2007•100 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
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 investigate the notion of quantum chromatic number of a graph, which is the minimal number of colours necessary in a protocol in which two separated provers can convince a referee that they have a colouring of the graph.After discussing this notion from first principles, we go on to establish relations with the clique number and orthogonal representations of the graph. We also prove several general facts about this graph parameter and find large separations between the clique number and the quantum chromatic number by looking at random graphs. Finally, we show that there can be no separation between classical and quantum chromatic number if the latter is 222, nor if it is 333 in a restricted quantum model; on the other hand, we exhibit a graph on 181818 vertices and 444444 edges with chromatic number 555 and quantum chromatic number 444.
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.