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 Electronic Journal of Combinatorics

On the Quantum Chromatic Number of a Graph

Peter J‎. Cameron, Ashley Montanaro, Michael Newman, Simone Severini B, Andreas Winter

Published Nov 28, 2007• 100 citations
Publisher

Abstract

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

DOI
10.37236/999

Related papers

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 an interrogator with certainty 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•Aug 1, 2006•3 citations

Spectral lower bounds for the quantum chromatic number of a graph

Paweł Wocjan, Clive H. Elphick

The quantum chromatic number, $χ_q(G)$, of a graph $G$ was originally defined as the minimal number of colors necessary in a quantum protocol in which two provers that cannot communicate with each other but share an entangled state can convince an interrogator with certainty that they have a coloring of the graph. We use an equivalent purely combinatorial definition of $χ_q(G)$ to prove that many spectral lower bounds for the chromatic number, $χ(G)$, are also lower bounds for $χ_q(G)$. This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.

arXiv:1805.08334•May 22, 2018•1 citation

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•1 citation

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

On the exact quantum chromatic number of generalized Johnson graphs

Gaojun Luo, Xiwang Cao, Shitao Li +1 more

The quantum chromatic number is a fundamental parameter in the study of nonlocal games, capturing the extent to which entanglement can improve performance in distributed tasks. In this paper, we investigate the quantum chromatic number of generalized Johnson graphs. By constructing modulus-one orthogonal representations, we obtain general upper bounds on their quantum chromatic numbers. We further analyze the smallest eigenvalue of these graphs. Combining the resulting Hoffman-type lower bounds with the upper bounds obtained from orthogonal representations, we determine the exact quantum chromatic numbers of two infinite families of generalized Johnson graphs. Finally, applying a forbidden-distance theorem for binary codes, we show that the classical chromatic numbers of these families grow exponentially with $n$, whereas their quantum chromatic numbers grow linearly. These families exhibit an exponential separation between the classical and quantum chromatic numbers.

arXiv:2609.04677•Sep 4, 2026•0 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
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 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 an interrogator with certainty 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 quantum chromatic number, χq(G)χ_q(G)χq​(G), of a graph GGG was originally defined as the minimal number of colors necessary in a quantum protocol in which two provers that cannot communicate with each other but share an entangled state can convince an interrogator with certainty that they have a coloring of the graph. We use an equivalent purely combinatorial definition of χq(G)χ_q(G)χq​(G) to prove that many spectral lower bounds for the chromatic number, χ(G)χ(G)χ(G), are also lower bounds for χq(G)χ_q(G)χq​(G). This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.
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.
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 is a fundamental parameter in the study of nonlocal games, capturing the extent to which entanglement can improve performance in distributed tasks. In this paper, we investigate the quantum chromatic number of generalized Johnson graphs. By constructing modulus-one orthogonal representations, we obtain general upper bounds on their quantum chromatic numbers. We further analyze the smallest eigenvalue of these graphs. Combining the resulting Hoffman-type lower bounds with the upper bounds obtained from orthogonal representations, we determine the exact quantum chromatic numbers of two infinite families of generalized Johnson graphs. Finally, applying a forbidden-distance theorem for binary codes, we show that the classical chromatic numbers of these families grow exponentially with nnn, whereas their quantum chromatic numbers grow linearly. These families exhibit an exponential separation between the classical and quantum chromatic numbers.
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.