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

Klasyczne i kwantowe grafy Knesera

Igor Chełstowski

Published Jan 1, 2026• 0 citations
OpenAlex

Abstract

We present a construction of quantum Kneser graphs, which yields classical Kneser graphs in the commutative case.We also generalize this construction to obtain quantum versions of generalized Kneser graphs, such as Johnson graphs.We discuss several basic properties of the constructed quantum graphs, such as their reflexivity and regularity.Then, we investigate their quantum chromatic numbers and establish upper bounds on them by constructing explicit colorings.We also investigate spectral lower bounds on quantum chromatic numbers for several examples and formulate a conjecture about their asymptotic behavior.Lastly, we present an alternate approach to quantization of Kneser graphs and a few results obtained for the quantum Mycielski construction.

Related papers

Quantum Mycielski graphs

Arkadiusz Bochniak, Paweł Kasprzak

The classical Mycielski transformation allows for constructing from a given graph a new one with an arbitrarily large chromatic number but preserving the size of the largest clique contained in it. This particular construction and its specific generalizations were widely discussed in graph theory literature. Here we propose an analog of these transformations for quantum graphs and study how they affect the (quantum) chromatic number as well as the clique numbers associated with them.

arXiv:2306.09994•Journal of Noncommutative Geometry•Sep 10, 2025•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•11 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

A counterexample to the quantum Hedetniemi conjecture

Julius A. Zeiss

Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs $G,H$ with \[ χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).\]The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital $C^*$-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and $C^*$-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.

math.COCross-listedarXiv:2609.20690•Sep 18, 2026•1 citation

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•4 citations

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
We present a construction of quantum Kneser graphs, which yields classical Kneser graphs in the commutative case.We also generalize this construction to obtain quantum versions of generalized Kneser graphs, such as Johnson graphs.We discuss several basic properties of the constructed quantum graphs, such as their reflexivity and regularity.Then, we investigate their quantum chromatic numbers and establish upper bounds on them by constructing explicit colorings.We also investigate spectral lower bounds on quantum chromatic numbers for several examples and formulate a conjecture about their asymptotic behavior.Lastly, we present an alternate approach to quantization of Kneser graphs and a few results obtained for the quantum Mycielski construction.
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 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.
Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs G,HG,HG,H with χ(G×H)≤1538<1539=min⁡(χq(G),χq(H)). χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).χ(G×H)≤1538<1539=min(χq​(G),χq​(H)).The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital C∗C^*C∗-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and C∗C^*C∗-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.
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.
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.