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

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

Giannicola Scarpa, Simone Severini B

Published Apr 1, 2012• 25 citations
OpenAlex

Abstract

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.

Related papers

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•21 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•34 citations

Oddities of Quantum Colorings

Laura Mančinska, David E. Roberson

The main purpose of this work is to collect some interesting facts related to quantum graph coloring.We consider the orthogonality graph of the three-dimensional vectors with entries from the set {-1, 0, 1}.If we ignore the overall sign of the vectors, this yields a graph on thirteen vertices, which we denote by G13.It turns out that G13 (or the graph obtained from this by adding an apex vertex) is the smallest known example which exhibits separations between several graph parameters.We are particularly interested in using G13 to separate quantum graph parameters from their classical counterparts.We give a proof that G13 is not quantum 3-colorable, which shows that its orthogonal rank is strictly less than its quantum chromatic number.This also proves, along with other previously known results, that adding an apex vertex to G13 does not change its quantum chromatic number.The graph G13 is the first and only known graph with either of these properties.Lastly, we investigate a graph construction used for taking instances of 3-SAT to instances of 3-COLORING.We show that any graph constructed in this manner has an orthogonal representation in dimension three if and only if it is 3-colorable.Since it has been previously shown that there are such graphs with quantum 3-colorings but no classical 3-colorings, it follows that quantum chromatic number can be strictly less than orthogonal rank.Together with the above, this proves that orthogonal rank and quantum chromatic number are not comparable as graph parameters.

arXiv:1801.03542•Baltic Journal of Modern Computing•Dec 19, 2016•2 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

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

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.

arXiv:2410.00042•Sep 27, 2024•0 citations
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 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.
The main purpose of this work is to collect some interesting facts related to quantum graph coloring.We consider the orthogonality graph of the three-dimensional vectors with entries from the set {-1, 0, 1}.If we ignore the overall sign of the vectors, this yields a graph on thirteen vertices, which we denote by G13.It turns out that G13 (or the graph obtained from this by adding an apex vertex) is the smallest known example which exhibits separations between several graph parameters.We are particularly interested in using G13 to separate quantum graph parameters from their classical counterparts.We give a proof that G13 is not quantum 3-colorable, which shows that its orthogonal rank is strictly less than its quantum chromatic number.This also proves, along with other previously known results, that adding an apex vertex to G13 does not change its quantum chromatic number.The graph G13 is the first and only known graph with either of these properties.Lastly, we investigate a graph construction used for taking instances of 3-SAT to instances of 3-COLORING.We show that any graph constructed in this manner has an orthogonal representation in dimension three if and only if it is 3-colorable.Since it has been previously shown that there are such graphs with quantum 3-colorings but no classical 3-colorings, it follows that quantum chromatic number can be strictly less than orthogonal rank.Together with the above, this proves that orthogonal rank and quantum chromatic number are not comparable as graph parameters.
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 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 compute the exact value of the quantum chromatic numbers of Hadamard graphs of order n=2Nn=2^Nn=2N for NNN a multiple of 444 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.