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.
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.
The paper addresses the quantum Hedetniemi conjecture: whether the quantum chromatic number satisfies χ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)}. The factors have 524,288 and 1,576,451 vertices. More strongly, χC∗(G)≥1639 and χC∗(H)=χ(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[K512], 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 ϑ(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,H with χ(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∗-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
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ε(ϱ) is the set of Pauli observables having expectation value magnitude at least ε in some given quantum state ϱ, then the fractional chromatic number of the anticommutation graph G induced by Bε(ϱ) is O(ε−2). In other words, it asserts that there exists a constant C such that χ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 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.
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 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-r quantum chromatic numbers. While it can now be shown that for every r, χq and χ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 G21 on 21 vertices with χ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 Gmsg on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies χq(Gmsg)=3 and χq(1)(Gmsg)=4. In addition, G21 provides the first provable separation between the parameters χq(1) and χq(2). We believe that our techniques for constructing 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}, 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 Sn−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 Sn−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 Sn−1 admits a rank-one quantum n-coloring if and only if n∈{2,4,8}, thereby settling a conjecture of Zeng and Zhang, as does the fact that for all m≥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.
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, 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≤Δ 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)≥4m+3π2m3/4 for all triangle-free graphs with m edges.