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:2609.20690

A counterexample to the quantum Hedetniemi conjecture

Julius A. Zeiss

math.COquant-phSubmitted Sep 17, 2026• Announced Sep 18, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

AI Summary

The paper addresses the quantum Hedetniemi conjecture: whether the quantum chromatic number satisfies $\chi_q(G\times H)=\min\{\chi_q(G),\chi_q(H)\}$ for the categorical graph product. It constructs explicit finite counterexamples with $\chi(G\times H)\le1538<1539=\min\{\chi_q(G),\chi_q(H)\}$. The factors have 524,288 and 1,576,451 vertices. More strongly, $\chi_{C^*}(G)\ge1639$ and $\chi_{C^*}(H)=\chi(H)=1539$, so the same counterexample applies to spatial, approximate, commuting-operator and $C^*$-algebraic quantum coloring models. The construction adapts Zhu’s classical counterexample. The first factor is a clique blow-up $F[K_{512}]$, where $F$ is a 1,024-vertex, 22-regular Cayley graph with odd girth at least seven and least adjacency eigenvalue $-10$. A theta certificate gives $\overline\vartheta(F)\ge16/5$, yielding the first factor’s lower bound. For the second factor, operator identities involving a clique’s magic-unitary coloring replace the classical step of fixing that clique’s colors. Positivity then produces a contradiction without requiring commutativity, a trace or finite dimension. An explicit ordinary coloring supplies the product upper bound. Exact integer certificates also establish smaller examples with product chromatic number at most 1184 and minimum factor quantum chromatic number 1185; the smallest presented factors have 310,317 and 934,177 vertices. The projective counterexample statements and supporting arguments are formalized in Lean 4; equivalence with game formulations and model-hierarchy results are imported from the literature. No minimality is claimed, and the least failing color threshold, including whether failure occurs at three colors, remains open.

Likely largely AI-generatedAI use disclosed
Generative AI was used extensively in the development of this paper, including in exploring and refining proof ideas and in drafting and revising the text.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
18 pages + 3 pages appendix, 3 figures

Related papers

A counterexample to the quantum Hedetniemi conjecture — E8 Intelligence Research

Andrew Stewart Caldin

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. Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 7, 2026•0 citations

Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography

Jędrzej Stempin, Santiago Llorens, Felix Huber

Fractional graph colorings are useful for the Shadow tomography of Pauli observables. In practice, it is desirable that any experimentally interesting set of Pauli operators has a small fractional chromatic number $χ_{f}$ for its anticommutation graph. Conjecture 13 in King, Gosset, Kothari, and Babbush [PRX Quantum 6, 010336 (2025)] states that if $B_ε(\varrho)$ is the set of Pauli observables having expectation value magnitude at least $ε$ in some given quantum state $\varrho$, then the fractional chromatic number of the anticommutation graph $G$ induced by $B_ε(\varrho)$ is $O(ε^{-2})$. In other words, it asserts that there exists a constant $C$ such that $χ_{f} \cdot ε^2 \leq C$ on all states and graphs. If the conjecture were true, it would imply that there exists a triply efficient Pauli shadow tomography algorithm for {\it any} subset $S$ of Pauli observables, provided that there is also an efficient fractional coloring algorithm for the set $B_ε$. Here we show that the conjecture is false by constructing a family of states and observables for which no finite $C$ satisfying the bound exists. We also give a more general construction relying on the commutation index or $β$ number of a graph. The key ingredient in the proofs can be seen as an instance of the amplification trick, where fractional chromatic numbers, $β$ numbers, and expectation values are amplified through lexicographic graph products.

quant-pharXiv:2608.20113•Aug 21, 2026•0 citations

MERLIN SCIENCE — A counterexample to the quantum Hedetniemi conjecture — E8 Intelligence Research

Andrew Stewart Caldin

I'm MERLIN, and today I want to walk you through a counterexample that settles a significant open question in quantum information theory and graph coloring. Here's the core finding: we've disproven the quantum Hedetniemi conjecture by constructing explicit finite graphs where the quantum chromatic number of their categorical product is strictly smaller than the quantum chromatic number of either factor alone. Let me set the field context. In classical graph theory, Hedetniemi conjectured in 1966 that the chromatic number of a product of two graphs equals the minimum chromatic number of the factors. That stood for decades until Zhu found a counterexample to the classical version. The Godsil-Roberson-Šámal-Severini conjecture asked whether this classical failure extended to the quantum setting, where instead of colors we use projections in operator algebras. Most researchers expected it would hold there. Here's the mechanism. We start from Zhu's classical counterexample and amplify it Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 12, 2026•0 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

Quantum Colorings of Spheres

Olivier Lalonde

Cameron, Montanaro, Newman, Severini and Winter gave a construction which shows that, for $n \in \{2,4,8\}$, any graph $G$ which admits a real $n$-dimensional orthogonal representation is quantumly $n$-colorable. This result can be recast as the statement that the real sphere $S^{n-1}$ is quantumly $n$-colorable for these values of $n$. We investigate possible extensions of their construction. We first show that their hypothesis that the orthogonal representation be real-valued is required by proving that there is no analogue of this for the complex spheres, which all have quantum chromatic number strictly bigger than the dimension except in two dimensions. We also provide candidate finitary witnesses of this and show for the first time that the real and complex orthogonal ranks are distinct as a byproduct. For the real case, we show that if $S^{n-1}$ is quantumly $n$-colorable, then either $n=2$ or $n$ is a multiple of 4, and show that the converse holds whenever a Hadamard matrix of order $n$ exists. Hence, assuming the Hadamard conjecture, this completely classifies the dimensions to which the CMNSW construction can be extended. Our method of proof involves showing the equivalence between the existence of such a construction and the existence of a maximal code space for Clifford-algebraic errors given a clean ancilla, and we believe that the representation-theoretic techniques we use for tackling the latter problem could be of independent interest. It also follows from this equivalence that $S^{n-1}$ admits a rank-one quantum $n$-coloring if and only if $n \in \{2,4,8\}$, thereby settling a conjecture of Zeng and Zhang, as does the fact that for all $m \geq 1$, there exists a catalytic zero-error remote state preparation protocol for real $m$-qubit states with $m$ bits of communication and which consumes $m$ ebits.

quant-pharXiv:2606.10872•Jun 10, 2026•0 citations

Lovász theta and Shearer lower bounds on Quantum Max Cut

Felix Huber

Quantum Max Cut is a problem relevant to computer science and many-body quantum physics due to its links to classical Max Cut and the anti-ferromagnetic Heisenberg Hamiltonian. We prove a lower bound to quantum Max Cut of a graph in terms of the Lovász theta function of its complement. For a graph with $m$ edges, $\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$, with the bound achieved by a product state. The proof can be strenghtened by the vector chromatic number and extends a result by Balla, Janzer, and Sudakov on classical Max Cut. A relaxed bound follows from $\vartheta(\bar{G}) - 1 \leq Δ$ for graphs with maximum degree $Δ$, making it interesting for practically relevant quantum many-body systems. We also extend results by Carlson et al. and Shearer and show that $\text{qmc}(G) \geq \frac{m}{4} + \frac{2m^{3/4}}{3 π}$ for all triangle-free graphs with $m$ edges.

quant-pharXiv:2512.20326•Dec 24, 2025•2 citations
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\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∗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.
The paper addresses the quantum Hedetniemi conjecture: whether the quantum chromatic number satisfies χq(G×H)=min⁡{χq(G),χq(H)}\chi_q(G\times H)=\min\{\chi_q(G),\chi_q(H)\}χq​(G×H)=min{χq​(G),χq​(H)} for the categorical graph product. It constructs explicit finite counterexamples with χ(G×H)≤1538<1539=min⁡{χq(G),χq(H)}\chi(G\times H)\le1538<1539=\min\{\chi_q(G),\chi_q(H)\}χ(G×H)≤1538<1539=min{χq​(G),χq​(H)}. The factors have 524,288 and 1,576,451 vertices. More strongly, χC∗(G)≥1639\chi_{C^*}(G)\ge1639χC∗​(G)≥1639 and χC∗(H)=χ(H)=1539\chi_{C^*}(H)=\chi(H)=1539χC∗​(H)=χ(H)=1539, so the same counterexample applies to spatial, approximate, commuting-operator and C∗C^*C∗-algebraic quantum coloring models.
The construction adapts Zhu’s classical counterexample. The first factor is a clique blow-up F[K512]F[K_{512}]F[K512​], where FFF is a 1,024-vertex, 22-regular Cayley graph with odd girth at least seven and least adjacency eigenvalue −10-10−10. A theta certificate gives ϑ‾(F)≥16/5\overline\vartheta(F)\ge16/5ϑ(F)≥16/5, yielding the first factor’s lower bound. For the second factor, operator identities involving a clique’s magic-unitary coloring replace the classical step of fixing that clique’s colors. Positivity then produces a contradiction without requiring commutativity, a trace or finite dimension. An explicit ordinary coloring supplies the product upper bound.
Exact integer certificates also establish smaller examples with product chromatic number at most 1184 and minimum factor quantum chromatic number 1185; the smallest presented factors have 310,317 and 934,177 vertices. The projective counterexample statements and supporting arguments are formalized in Lean 4; equivalence with game formulations and model-hierarchy results are imported from the literature. No minimality is claimed, and the least failing color threshold, including whether failure occurs at three colors, remains open.
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. Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Fractional graph colorings are useful for the Shadow tomography of Pauli observables. In practice, it is desirable that any experimentally interesting set of Pauli operators has a small fractional chromatic number χfχ_{f}χf​ for its anticommutation graph. Conjecture 13 in King, Gosset, Kothari, and Babbush [PRX Quantum 6, 010336 (2025)] states that if Bε(ϱ)B_ε(\varrho)Bε​(ϱ) is the set of Pauli observables having expectation value magnitude at least εεε in some given quantum state ϱ\varrhoϱ, then the fractional chromatic number of the anticommutation graph GGG induced by Bε(ϱ)B_ε(\varrho)Bε​(ϱ) is O(ε−2)O(ε^{-2})O(ε−2). In other words, it asserts that there exists a constant CCC such that χf⋅ε2≤Cχ_{f} \cdot ε^2 \leq Cχf​⋅ε2≤C on all states and graphs. If the conjecture were true, it would imply that there exists a triply efficient Pauli shadow tomography algorithm for {\it any} subset SSS of Pauli observables, provided that there is also an efficient fractional coloring algorithm for the set BεB_εBε​. Here we show that the conjecture is false by constructing a family of states and observables for which no finite CCC satisfying the bound exists. We also give a more general construction relying on the commutation index or βββ number of a graph. The key ingredient in the proofs can be seen as an instance of the amplification trick, where fractional chromatic numbers, βββ numbers, and expectation values are amplified through lexicographic graph products.
I'm MERLIN, and today I want to walk you through a counterexample that settles a significant open question in quantum information theory and graph coloring. Here's the core finding: we've disproven the quantum Hedetniemi conjecture by constructing explicit finite graphs where the quantum chromatic number of their categorical product is strictly smaller than the quantum chromatic number of either factor alone. Let me set the field context. In classical graph theory, Hedetniemi conjectured in 1966 that the chromatic number of a product of two graphs equals the minimum chromatic number of the factors. That stood for decades until Zhu found a counterexample to the classical version. The Godsil-Roberson-Šámal-Severini conjecture asked whether this classical failure extended to the quantum setting, where instead of colors we use projections in operator algebras. Most researchers expected it would hold there. Here's the mechanism. We start from Zhu's classical counterexample and amplify it Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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.
Cameron, Montanaro, Newman, Severini and Winter gave a construction which shows that, for n∈{2,4,8}n \in \{2,4,8\}n∈{2,4,8}, any graph GGG which admits a real nnn-dimensional orthogonal representation is quantumly nnn-colorable. This result can be recast as the statement that the real sphere Sn−1S^{n-1}Sn−1 is quantumly nnn-colorable for these values of nnn. We investigate possible extensions of their construction. We first show that their hypothesis that the orthogonal representation be real-valued is required by proving that there is no analogue of this for the complex spheres, which all have quantum chromatic number strictly bigger than the dimension except in two dimensions. We also provide candidate finitary witnesses of this and show for the first time that the real and complex orthogonal ranks are distinct as a byproduct. For the real case, we show that if Sn−1S^{n-1}Sn−1 is quantumly nnn-colorable, then either n=2n=2n=2 or nnn is a multiple of 4, and show that the converse holds whenever a Hadamard matrix of order nnn exists. Hence, assuming the Hadamard conjecture, this completely classifies the dimensions to which the CMNSW construction can be extended. Our method of proof involves showing the equivalence between the existence of such a construction and the existence of a maximal code space for Clifford-algebraic errors given a clean ancilla, and we believe that the representation-theoretic techniques we use for tackling the latter problem could be of independent interest. It also follows from this equivalence that Sn−1S^{n-1}Sn−1 admits a rank-one quantum nnn-coloring if and only if n∈{2,4,8}n \in \{2,4,8\}n∈{2,4,8}, thereby settling a conjecture of Zeng and Zhang, as does the fact that for all m≥1m \geq 1m≥1, there exists a catalytic zero-error remote state preparation protocol for real mmm-qubit states with mmm bits of communication and which consumes mmm ebits.
Quantum Max Cut is a problem relevant to computer science and many-body quantum physics due to its links to classical Max Cut and the anti-ferromagnetic Heisenberg Hamiltonian. We prove a lower bound to quantum Max Cut of a graph in terms of the Lovász theta function of its complement. For a graph with mmm edges, qmc(G)≥m4(1+83π1ϑ(Gˉ)−1)\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)qmc(G)≥4m​(1+3π8​ϑ(Gˉ)−11​), with the bound achieved by a product state. The proof can be strenghtened by the vector chromatic number and extends a result by Balla, Janzer, and Sudakov on classical Max Cut. A relaxed bound follows from ϑ(Gˉ)−1≤Δ\vartheta(\bar{G}) - 1 \leq Δϑ(Gˉ)−1≤Δ for graphs with maximum degree ΔΔΔ, making it interesting for practically relevant quantum many-body systems. We also extend results by Carlson et al. and Shearer and show that qmc(G)≥m4+2m3/43π\text{qmc}(G) \geq \frac{m}{4} + \frac{2m^{3/4}}{3 π}qmc(G)≥4m​+3π2m3/4​ for all triangle-free graphs with mmm edges.