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:2503.23207 · Society for Industrial and Applied Mathematics eBooks

On the Quantum Chromatic Gap

Lorenzo Ciardo

Published Jan 1, 2026• 0 citations
arXivHTMLPDF

Abstract

The largest known gap between quantum and classical chromatic number of graphs, obtained via quantum protocols for colouring Hadamard graphs based on the Deutsch–Jozsa algorithm and the quantum Fourier transform, is exponential. We put forth a quantum pseudo-telepathy version of Khot’s \(d\)-to-1 Games Conjecture and prove that, conditional on its validity, the gap is unbounded: There exist graphs whose quantum chromatic number is 3 and whose classical chromatic number is arbitrarily large. Furthermore, we show that the existence of a certain form of pseudo-telepathic XOR games would imply the conjecture and, thus, the unboundedness of the quantum chromatic gap. As two technical steps of our proof that might be of independent interest, we establish a quantum adjunction theorem for Pultr functors between categories of relational structures, and we prove that the Dinur–Khot–Kindler–Minzer–Safra reduction, recently used for proving the 2-to-2 Games Theorem, is quantum complete.

DOI
10.1137/1.9781611978971.121

Related papers

On the Quantum Chromatic Gap II

Lorenzo Ciardo, Antoine Mottet

We confirm a conjecture of the first author [SODA'26] on a strong form of pseudo-telepathy for Khot's $d$-to-$1$ games: for every $d\geq 4$, every $ε>0$, and every $k\in\mathbb N$, there is a $d$-to-$1$ label-cover game of classical value less than $ε$ that admits a perfect quantum strategy using finite-dimensional shared entanglement with measurement contexts of radius at least $k$. As a consequence, there exist graphs whose quantum chromatic number $χ_q$ is $3$ and whose classical chromatic number $χ$ is arbitrarily large. This is the first improvement on the quantum chromatic gap since the work of Brassard, Cleve, and Tapp [Phys. Rev. Lett.'99], which produced graphs for which $χ$ grows exponentially in $χ_q$. To prove the conjecture, we proceed as follows. We start with a ``stretched'' version of the Mermin--Peres magic square, obtained by spacing out its equations and linking them with additional long equation wires. This operation increases the radius of the initial measurement contexts of a perfect quantum strategy for the game, while preserving classical unsatisfiability. We then apply parallel repetition to make the classical value small, and we turn the system into a pseudo-telepathic multi-layered Kneser hypergraph via a PCP construction of Dinur, Guruswami, Khot, and Regev [STOC'03]. Finally, we feed the resulting hypergraph into the reduction of Fei, Minzer, and Wang from hypergraph colouring to $4$-to-$1$ games, we establish quantum completeness of this reduction, and we show that it preserves context radius.

quant-pharXiv:2610.40571•Oct 30, 2026•0 citations

A Quantum Protocol to Win the Graph Colouring Game on All Hadamard Graphs

David Avis

This paper deals with graph colouring games, an example of pseudo-telepathy, in which two provers can convince a verifier that a graph $G$ is $c$-colourable where $c$ is less than the chromatic number of the graph. They win the game if they convince the verifier. It is known that the players cannot win if they share only classical information, but they can win in some cases by sharing entanglement. The smallest known graph where the players win in the quantum setting, but not in the classical setting, was found by Galliard, Tapp and Wolf and has 32,768 vertices. It is a connected component of the Hadamard graph $G_N$ with $N=c=16$. Their protocol applies only to Hadamard graphs where $N$ is a power of 2. We propose a protocol that applies to all Hadamard graphs. Combined with a result of Frankl, this shows that the players can win on any induced subgraph of $G_{12}$ having 1609 vertices, with $c=12$. Combined with a result of Frankl and Rodl, our result shows that all sufficiently large Hadamard graphs yield pseudo-telepathy games.

arXiv:quant-ph/0509047•IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•May 1, 2006•36 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

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

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

Entanglement and Non-locality in Games and Graphs

Arthur Mehta

Quantum graph theory, also known as non-commutative graph theory, is an operator space generalization of graph theory. The independence number, and Lovasz theta function were generalized to this setting by Duan, Severini, and Winter [DSW13] and two different version of the chromatic number were introduced by Stahlke [Sta16] and Paulsen [HPP16]. We introduce two new generalizations of the chromatic number to non-commutative graphs and provide an upper bound on the parameter of Stahlke. We provide a generalization of the graph complement and show the chromatic number of the orthogonal complement of a non-commutative graph is bounded below by its theta number. We also provide a generalization of both Sabidussi's Theorem and Hedetniemi's conjecture to non-commutative graphs. The study of non-local games considers scenarios in which separated players collaborate to provide satisfying responses to questions given by a referee. The condition of separating players makes non-local games an excellent setting to gain insight into quantum phenomena such as entanglement and non-locality. Non-local games can also provide protocols known as self-tests. Self-testing allows an experimenter to interact classically with a black box quantum system and certify that a specific entangled state was present and a specific set of measurements were performed. The most studied self-test is the CHSH game which certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. We introduce an algebraic generalization of CHSH and obtain a self-test for non-Pauli operators resolving an open question posed by Coladangelo and Stark (QIP 2017). Our games also provide a self-test for states other than the maximally entangled state, and hence resolves the open question posed by Cleve and Mittal (ICALP 2012). This thesis is primarily based on two collaborative works written by the author and several coauthors [CMMN20], [KM19].

•Jun 1, 2021•0 citations
The largest known gap between quantum and classical chromatic number of graphs, obtained via quantum protocols for colouring Hadamard graphs based on the Deutsch–Jozsa algorithm and the quantum Fourier transform, is exponential. We put forth a quantum pseudo-telepathy version of Khot’s (d)-to-1 Games Conjecture and prove that, conditional on its validity, the gap is unbounded: There exist graphs whose quantum chromatic number is 3 and whose classical chromatic number is arbitrarily large. Furthermore, we show that the existence of a certain form of pseudo-telepathic XOR games would imply the conjecture and, thus, the unboundedness of the quantum chromatic gap. As two technical steps of our proof that might be of independent interest, we establish a quantum adjunction theorem for Pultr functors between categories of relational structures, and we prove that the Dinur–Khot–Kindler–Minzer–Safra reduction, recently used for proving the 2-to-2 Games Theorem, is quantum complete.
We confirm a conjecture of the first author [SODA'26] on a strong form of pseudo-telepathy for Khot's ddd-to-111 games: for every d≥4d\geq 4d≥4, every ε>0ε>0ε>0, and every k∈Nk\in\mathbb Nk∈N, there is a ddd-to-111 label-cover game of classical value less than εεε that admits a perfect quantum strategy using finite-dimensional shared entanglement with measurement contexts of radius at least kkk. As a consequence, there exist graphs whose quantum chromatic number χqχ_qχq​ is 333 and whose classical chromatic number χχχ is arbitrarily large. This is the first improvement on the quantum chromatic gap since the work of Brassard, Cleve, and Tapp [Phys. Rev. Lett.'99], which produced graphs for which χχχ grows exponentially in χqχ_qχq​. To prove the conjecture, we proceed as follows. We start with a ``stretched'' version of the Mermin--Peres magic square, obtained by spacing out its equations and linking them with additional long equation wires. This operation increases the radius of the initial measurement contexts of a perfect quantum strategy for the game, while preserving classical unsatisfiability. We then apply parallel repetition to make the classical value small, and we turn the system into a pseudo-telepathic multi-layered Kneser hypergraph via a PCP construction of Dinur, Guruswami, Khot, and Regev [STOC'03]. Finally, we feed the resulting hypergraph into the reduction of Fei, Minzer, and Wang from hypergraph colouring to 444-to-111 games, we establish quantum completeness of this reduction, and we show that it preserves context radius.
This paper deals with graph colouring games, an example of pseudo-telepathy, in which two provers can convince a verifier that a graph GGG is ccc-colourable where ccc is less than the chromatic number of the graph. They win the game if they convince the verifier. It is known that the players cannot win if they share only classical information, but they can win in some cases by sharing entanglement. The smallest known graph where the players win in the quantum setting, but not in the classical setting, was found by Galliard, Tapp and Wolf and has 32,768 vertices. It is a connected component of the Hadamard graph GNG_NGN​ with N=c=16N=c=16N=c=16. Their protocol applies only to Hadamard graphs where NNN is a power of 2. We propose a protocol that applies to all Hadamard graphs. Combined with a result of Frankl, this shows that the players can win on any induced subgraph of G12G_{12}G12​ having 1609 vertices, with c=12c=12c=12. Combined with a result of Frankl and Rodl, our result shows that all sufficiently large Hadamard graphs yield pseudo-telepathy games.
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.
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.
Quantum graph theory, also known as non-commutative graph theory, is an operator space generalization of graph theory. The independence number, and Lovasz theta function were generalized to this setting by Duan, Severini, and Winter [DSW13] and two different version of the chromatic number were introduced by Stahlke [Sta16] and Paulsen [HPP16]. We introduce two new generalizations of the chromatic number to non-commutative graphs and provide an upper bound on the parameter of Stahlke. We provide a generalization of the graph complement and show the chromatic number of the orthogonal complement of a non-commutative graph is bounded below by its theta number. We also provide a generalization of both Sabidussi's Theorem and Hedetniemi's conjecture to non-commutative graphs. The study of non-local games considers scenarios in which separated players collaborate to provide satisfying responses to questions given by a referee. The condition of separating players makes non-local games an excellent setting to gain insight into quantum phenomena such as entanglement and non-locality. Non-local games can also provide protocols known as self-tests. Self-testing allows an experimenter to interact classically with a black box quantum system and certify that a specific entangled state was present and a specific set of measurements were performed. The most studied self-test is the CHSH game which certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. We introduce an algebraic generalization of CHSH and obtain a self-test for non-Pauli operators resolving an open question posed by Coladangelo and Stark (QIP 2017). Our games also provide a self-test for states other than the maximally entangled state, and hence resolves the open question posed by Cleve and Mittal (ICALP 2012). This thesis is primarily based on two collaborative works written by the author and several coauthors [CMMN20], [KM19].