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:1106.0712 · IEEE Transactions on Information Theory

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

Giannicola Scarpa, Simone Severini B

Published Dec 5, 2011• 21 citations
arXivHTMLPDF

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

DOI
10.1109/tit.2011.2178018

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•25 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

Chromatic Quantum Contextuality

Karl Svozil

Chromatic quantum contextuality is a criterion of quantum nonclassicality based on (hyper)graph coloring constraints. If a quantum hypergraph requires more colors than the number of outcomes per maximal observable (context), it lacks a classical realization with n-uniform outcomes per context. Consequently, it cannot represent a “completable” noncontextual set of coexisting n-ary outcomes per maximal observable. This result serves as a chromatic analogue of the Kochen-Specker theorem. We present an explicit example of a four-colorable quantum logic in dimension three. Furthermore, chromatic contextuality suggests a novel restriction on classical truth values, thereby excluding two-valued measures that cannot be extended to n-ary colorings. Using this framework, we establish new bounds for the house, pentagon, and pentagram hypergraphs, refining previous constraints.

arXiv:2501.15261•Entropy•Apr 5, 2025•1 citation
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.
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.
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.
Chromatic quantum contextuality is a criterion of quantum nonclassicality based on (hyper)graph coloring constraints. If a quantum hypergraph requires more colors than the number of outcomes per maximal observable (context), it lacks a classical realization with n-uniform outcomes per context. Consequently, it cannot represent a “completable” noncontextual set of coexisting n-ary outcomes per maximal observable. This result serves as a chromatic analogue of the Kochen-Specker theorem. We present an explicit example of a four-colorable quantum logic in dimension three. Furthermore, chromatic contextuality suggests a novel restriction on classical truth values, thereby excluding two-valued measures that cannot be extended to n-ary colorings. Using this framework, we establish new bounds for the house, pentagon, and pentagram hypergraphs, refining previous constraints.