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:2401.16518

Quantum independence and chromatic numbers

Godsil, Chris, Sobchuk, Mariia

Published Jan 29, 2024• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2401.16518

Related papers

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.

•Apr 1, 2012•26 citations

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 χq(1)(G), which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number χ(G) and the minimum dimension of orthogonal representations ξ(G). It is known that ξ(G) ≤ χq(1)(G) ≤ χ(G). We answer three open questions about these relations: we give a necessary and sufficient condition to have ξ(G) = χq(1)(G), we exhibit a class of graphs such that ξ(G) ≤ χq(1)(G), and we give a necessary and sufficient condition to have χq(1)(G) ≤ χ(G). Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of contextuality 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 et al on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.

arXiv:1106.0712•IEEE Transactions on Information Theory•Dec 5, 2011•24 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$.

arXiv:quant-ph/0608016•The Electronic Journal of Combinatorics•Nov 28, 2007•119 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.

arXiv:2311.08194•The Electronic Journal of Combinatorics•Feb 14, 2025•11 citations

New Separations in Zero-Error Channel Capacity Through Projective Kochen–Specker Sets and Quantum Coloring

Laura Mančinska, G. Scarpa, Simone Severini B

We introduce two generalizations of Kochen-Specker (KS) sets: projective KS sets and generalized KS sets. We then use projective KS sets to characterize all graphs for which the chromatic number is strictly larger than the quantum chromatic number. Here, the quantum chromatic number is defined via a nonlocal game based on graph coloring. We further show that from any graph with separation between these two quantities, one can construct a classical channel for which entanglement assistance increases the one-shot zero-error capacity. As an example, we exhibit a new family of classical channels with an exponential increase.

arXiv:1207.1111•IEEE Transactions on Information Theory•Feb 20, 2013•31 citations

Quantum Graph Theory by Example

Gian Luca Spitzer, Ion Nechita

Quantum graphs have been introduced by Duan, Severini, and Winter to describe the zero-error behaviour of quantum channels. Since then, quantum graph theory has become a field of study in its own right. A substantial source of difficulty in working with quantum graphs compared to classical graphs stems from the fact that they are no longer discrete objects. This makes it generally difficult to construct insightful, non-trivial examples. We present a collection of non-trivial quantum graphs that can be thought of in discrete terms, and that can be expressed in the diagrammatic formalism introduced by Musto, Reutter, and Verdon. The examples arise as the quantum graphs acted on by increasingly smaller classical matrix groups, and are parametrised by triples of matrices $(A, B, C)$. The parametrisation reveals a clean decomposition of quantum graph structure into classical and genuinely quantum components: $A$ and $C$ are described by a classical weighted graph called the strange graph, while $B$ provides a purely quantum contribution with no classical analogue. Based on this model, we give exact formulas or establish bounds for quantum graph parameters, such as the number of connected components, the chromatic number, the independence number, and the clique number. Our results provide the first large, parametric families of quantum graphs for which standard graph parameters can be computed analytically.

math.OACross-listedarXiv:2603.23651•Quantum•Mar 26, 2026•1 citation
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.
The quantum chromatic number of a graph GGG 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 χq(1)(G)\chi_q^{(1)}(G)χq(1)​(G), which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number χ(G)\chi(G)χ(G) and the minimum dimension of orthogonal representations ξ(G)\xi(G)ξ(G). It is known that ξ(G)≤χq(1)(G)≤χ(G)\xi(G) \leq \chi_q^{(1)}(G) \leq \chi(G)ξ(G)≤χq(1)​(G)≤χ(G). We answer three open questions about these relations: we give a necessary and sufficient condition to have ξ(G)=χq(1)(G)\xi(G) = \chi_q^{(1)}(G)ξ(G)=χq(1)​(G), we exhibit a class of graphs such that ξ(G)<χq(1)(G)\xi(G) < \chi_q^{(1)}(G)ξ(G)<χq(1)​(G), and we give a necessary and sufficient condition to have χq(1)(G)<χ(G)\chi_q^{(1)}(G) < \chi(G)χq(1)​(G)<χ(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 χq(1)(G), which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number χ(G) and the minimum dimension of orthogonal representations ξ(G). It is known that ξ(G) ≤ χq(1)(G) ≤ χ(G). We answer three open questions about these relations: we give a necessary and sufficient condition to have ξ(G) = χq(1)(G), we exhibit a class of graphs such that ξ(G) ≤ χq(1)(G), and we give a necessary and sufficient condition to have χq(1)(G) ≤ χ(G). Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of contextuality 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 et al on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.
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 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 G14G_{14}G14​ 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-rrr quantum chromatic numbers. While it can now be shown that for every rrr, χq\chi_qχq​ and χq(r)\chi^{(r)}_qχq(r)​ 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 G21G_{21}G21​ on 21 vertices with χq(G21)=χq(2)(G21)=4\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4χq​(G21​)=χq(2)​(G21​)=4 and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph GmsgG_{msg}Gmsg​ on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies χq(Gmsg)=3\chi_q(G_{msg}) = 3χq​(Gmsg​)=3 and χq(1)(Gmsg)=4\chi^{(1)}_q(G_{msg}) = 4χq(1)​(Gmsg​)=4. In addition, G21G_{21}G21​ provides the first provable separation between the parameters χq(1)\chi^{(1)}_qχq(1)​ and χq(2)\chi^{(2)}_qχq(2)​. We believe that our techniques for constructing G21G_{21}G21​ and lower bounding its orthogonal rank could be of independent interest.
We introduce two generalizations of Kochen-Specker (KS) sets: projective KS sets and generalized KS sets. We then use projective KS sets to characterize all graphs for which the chromatic number is strictly larger than the quantum chromatic number. Here, the quantum chromatic number is defined via a nonlocal game based on graph coloring. We further show that from any graph with separation between these two quantities, one can construct a classical channel for which entanglement assistance increases the one-shot zero-error capacity. As an example, we exhibit a new family of classical channels with an exponential increase.
Quantum graphs have been introduced by Duan, Severini, and Winter to describe the zero-error behaviour of quantum channels. Since then, quantum graph theory has become a field of study in its own right. A substantial source of difficulty in working with quantum graphs compared to classical graphs stems from the fact that they are no longer discrete objects. This makes it generally difficult to construct insightful, non-trivial examples. We present a collection of non-trivial quantum graphs that can be thought of in discrete terms, and that can be expressed in the diagrammatic formalism introduced by Musto, Reutter, and Verdon. The examples arise as the quantum graphs acted on by increasingly smaller classical matrix groups, and are parametrised by triples of matrices (A,B,C)(A, B, C)(A,B,C). The parametrisation reveals a clean decomposition of quantum graph structure into classical and genuinely quantum components: AAA and CCC are described by a classical weighted graph called the strange graph, while BBB provides a purely quantum contribution with no classical analogue. Based on this model, we give exact formulas or establish bounds for quantum graph parameters, such as the number of connected components, the chromatic number, the independence number, and the clique number. Our results provide the first large, parametric families of quantum graphs for which standard graph parameters can be computed analytically.