⚛️ quantum physics

A counterexample to the quantum Hedetniemi conjecture

This paper disproves the Godsil-Roberson-Šamal-Severini conjecture on the quantum Hedetniemi conjecture by constructing explicit finite graphs where the quantum chromatic number of their categorical product is strictly less than the minimum of the quantum chromatic numbers of the individual factors, thereby demonstrating the failure of the conjecture across all major variants of quantum chromatic numbers.

Original authors: Julius A. Zeiss

Published 2026-09-18

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Julius A. Zeiss

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of mathematics, there is a long-standing puzzle about how to color maps and networks. Imagine a network of points connected by lines, like a subway map or a social network. The goal is to assign a color to every point so that no two points connected by a line share the same color. The minimum number of colors needed to do this is called the chromatic number. For decades, mathematicians wondered if there was a simple rule for what happens when you combine two such networks. Specifically, if you take two networks and weave them together into a single, larger structure, does the number of colors needed for the new structure simply match the easier of the two original networks? This idea, known as Hedetniemi's conjecture, seemed intuitively true and held up for many types of networks. However, in 2019, it was proven false for standard coloring, shattering the belief that the rule was universal.

But the story did not end there. In the realm of quantum physics, where particles can be linked in mysterious ways that defy classical logic, scientists developed a new version of this coloring game. In this quantum version, two players, Alice and Bob, try to color a network without talking to each other, but they can share a special quantum connection called entanglement. This connection allows them to coordinate their answers in ways that are impossible for ordinary people. The question arose: does the same rule hold for this quantum version? If you combine two quantum networks, is the number of colors needed determined by the easier one? This question, known as the quantum Hedetniemi conjecture, remained open for years, with many experts believing the rule would hold true even in the strange quantum world.

A researcher at RWTH Aachen University has now settled this question with a definitive "no." By constructing two incredibly large and complex networks, the author has proven that the quantum rule fails just as it did for the classical one. The discovery shows that when you weave two specific quantum networks together, the resulting structure can be colored with far fewer colors than either of the original networks could be colored on its own. This result is not a guess or a simulation; it is a rigorous mathematical proof that has been verified by computer software to ensure absolute accuracy. The finding forces a rethinking of how quantum entanglement interacts with the fundamental structure of networks, revealing that the quantum world allows for a kind of efficiency in coloring that simply does not exist in the classical world.

To understand the achievement, one must first grasp the setup. The researcher built two specific graphs, which are mathematical structures made of points and lines. The first graph, let's call it Graph G, was constructed by taking a base network of over a thousand points and replacing every single point with a massive cluster of 512 points all connected to each other. This created a graph with over half a million points. The second graph, Graph H, was a different, even larger structure with over 1.5 million points, designed with a very specific internal logic involving "anchors" and "lists" of allowed colors. The researcher then combined these two massive graphs into a single product graph, where every point in Graph G is paired with every point in Graph H.

The breakthrough came when the researcher analyzed how many colors were needed for this combined product. They demonstrated that the product graph could be successfully colored using only 1,538 colors. This number is surprisingly low given the size of the networks. However, the true shock lay in the analysis of the original graphs. When the researcher tried to color Graph G or Graph H individually using the rules of quantum coloring, they found it was impossible to do so with 1,538 colors or fewer. In fact, Graph G requires at least 1,639 colors, and Graph H requires exactly 1,539 colors. This creates a situation where the combined network is easier to color than either of its parts.

This outcome directly contradicts the quantum Hedetniemi conjecture, which predicted that the combined network would require at least as many colors as the easier of the two original networks. The proof relies on the unique properties of quantum mechanics, specifically the ability of entangled particles to coordinate in ways that classical systems cannot. The researcher showed that while the individual networks are too complex to be colored with 1,538 colors, the specific way they are woven together allows the quantum players to exploit their entanglement to find a solution that uses fewer colors. It is a bit like finding that two difficult puzzles, when glued together in a specific way, suddenly become easier to solve than either puzzle was on its own.

The significance of this work extends beyond just solving a puzzle. It confirms that quantum resources can fundamentally change the properties of mathematical structures in ways that classical intuition cannot predict. The researcher did not just find a small exception; they built a counterexample so large and complex that it required the use of a computer to verify the underlying calculations. The entire proof, including the construction of the graphs and the verification of the coloring properties, was checked by a formal proof assistant, a type of software that acts as a mathematical referee to ensure every logical step is flawless. This level of verification gives the result an unshakeable certainty.

The paper also explores the boundaries of this phenomenon. The researcher noted that for very small networks, the rule might still hold, but for larger, more complex structures, the quantum advantage breaks the pattern. The specific graphs used in the proof are massive, with hundreds of thousands of points, but the principle applies to the general case. The work also touches on different models of quantum mechanics, showing that this failure of the rule happens across various interpretations of how quantum systems work, making the result robust and widely applicable.

In the end, this research closes a chapter on a question that had puzzled mathematicians and physicists for years. It demonstrates that the quantum world does not simply follow the rules of the classical world, even in the abstract realm of graph coloring. The quantum Hedetniemi conjecture is false, and the proof stands as a testament to the power of combining deep mathematical theory with modern computational verification. The discovery leaves the field with a new understanding: in the quantum realm, the whole can indeed be simpler than the sum of its parts.

Technical Summary: A Counterexample to the Quantum Hedetniemi Conjecture

Problem Statement
The paper addresses the quantum Hedetniemi conjecture, a proposed extension of the classical Hedetniemi conjecture to quantum graph parameters. The classical conjecture, asserting that the chromatic number of the categorical product of two graphs equals the minimum of their individual chromatic numbers ( $\chi(G \times H) = \min\{\chi(G), \chi(H)\}$ ), was recently disproved by Shitov and Zhu.

Godsil, Roberson, Samal, and Severini previously established that an analogous equality holds for the Lovász theta number of the complement ( $\bar{\vartheta}$ ) and the vector chromatic number ( $\chi_{\rm vec}$ ). They conjectured that the equality also holds for the quantum chromatic number ( $\chi_q$ ) and the $C^{*}$ -chromatic number ( $\chi_{C^{*}}$ ):
$\chi_{q}(G\times H)=\min\{\chi_{q}(G),\chi_{q}(H)\}$
This paper demonstrates that this equality fails for specific instances. Specifically, the author constructs graphs $G$ and $H$ such that $\chi(G \times H)$ is strictly less than $\min\{\chi_{C^{*}}(G), \chi_{C^{*}}(H)\}$ , thereby refuting the conjecture for all parameters $\pi$ satisfying $\chi_{C^{*}} \leq \pi \leq \chi$ , including $\chi_q$ , $\chi_{qs}$ , $\chi_{qa}$ , and $\chi_{qc}$ . The paper notes that the conjecture holds trivially for $c \leq 2$ .

Methodology
The counterexample is constructed using a modification of Zhu's method for the classical case, adapted to the quantum setting. The construction relies on two specific graphs, $G$ and $H$ , defined via a base graph $F$ and an integer parameter $t$ .

Graph Construction:
- $G = F[K_t]$ : The lexicographic product of a base graph $F$ and a complete graph $K_t$ . This replaces every vertex of $F$ with a clique of size $t$ .
- $H = H_t$ : A graph constructed by Zhu, featuring a clique of "anchors" (size $c$ ), a "center" vertex, and specific cliques and matchings designed to force high chromatic numbers.
- Parameters: Let $p = 2t$ and $c = 3t + 2$ . The base graph $F$ must have $p$ vertices, no closed walks of length 3 or 5 (implying odd girth $\geq 7$ ), and satisfy a specific spectral condition involving a positive-semidefinite matrix $M$ supported on $F$ :
  $t \cdot \operatorname{sum}(M) > c \cdot \operatorname{tr}(M)$
Lower Bound Strategy (The First Factor $G$ ):
The author proves that $G$ cannot be colored with $c$ colors in any nonzero unital $C^{*}$ -algebra. They utilize a new bound derived from the Lovász theta number $\bar{\vartheta}$ .
- Lemma 5: Establishes that if a graph $X$ has a $k$ -coloring in a $C^{*}$ -algebra, then for any real positive-semidefinite matrix $M$ supported on $X$ , $\operatorname{sum}(M) \leq k \cdot \operatorname{tr}(M)$ .
- Corollary 6: Extends this to $F[K_t]$ , showing that a $k$ -coloring implies $t \cdot \operatorname{sum}(M) \leq k \cdot \operatorname{tr}(M)$ .
- By selecting a base graph $F$ where the ratio $\operatorname{sum}(M)/\operatorname{tr}(M)$ is sufficiently large (specifically $> c/t$ ), they force the lower bound $\chi_{C^{*}}(G) > c$ .
Lower Bound Strategy (The Second Factor $H$ ):
The author adapts Zhu's combinatorial argument to the $C^{*}$ -algebra setting.
- Instead of assigning discrete colors, they define operators $D_{v,b}$ representing the "event" that vertex $v$ takes the color of anchor $e_b$ .
- Using the properties of projections in a $C^{*}$ -algebra (specifically positivity and orthogonality relations), they derive identities that mimic the counting argument of the classical proof.
- They show that assuming a $c$ -coloring exists leads to a contradiction where a positive operator $\Phi$ must satisfy $-\Phi^2 \geq 0$ , forcing $\Phi = 0$ , which eventually implies the identity operator is zero, a contradiction in a nonzero algebra.
Upper Bound Strategy (The Product $G \times H$ ):
The author constructs an explicit ordinary $c$ -coloring for the product graph $G \times H$ . This relies on the structural properties of $F$ (no 3- or 5-cycles) to define maps $\psi_y: V(G) \to [c]$ for each $y \in V(H)$ such that adjacent vertices in the product receive different colors.

Key Contributions and Results

Disproof of the Conjecture: The paper provides a counterexample to the quantum Hedetniemi conjecture, showing it fails for parameters in the range $\chi_{C^{*}} \leq \pi \leq \chi$ .
Explicit Counterexample (Theorem 1):
- Base Graph $F$ : A Cayley graph on $\mathbb{F}_2^{10}$ with 1024 vertices, defined by a specific connection set $S$ . It is 22-regular with a least eigenvalue of $-10$.
- Parameters: $t = 512$ , $c = 1538$ .
- Graphs: $G = F[K_{512}]$ (524,288 vertices) and $H = H_{512}$ (1,576,451 vertices).
- Result: $\chi(G \times H) \leq 1538$ , while $\chi_{C^{*}}(G) \geq 1639$ and $\chi_{C^{*}}(H) = 1539$ .
- Conclusion: For any parameter $\pi$ between $\chi_{C^{*}}$ and $\chi$ , $\pi(G \times H) \leq 1538 < 1539 \leq \min\{\pi(G), \pi(H)\}$ .
Smaller Counterexamples (Appendix A): The author provides a smaller instance with $t=394$ and $c=1184$ , using a base graph of order 788, and a further reduced example with 310,317 vertices in the first factor.
Formal Verification: All theorems, lemmas, and propositions have been formally verified using the Lean 4 proof assistant with the Mathlib library. The verification covers the projective formulation of quantum coloring and the parameters $\chi$ , $\chi_q$ , and $\chi_{C^{*}}$ .
AI Disclosure: The author explicitly states that the core proof idea and the construction of the counterexample were proposed by a generative AI system, which the author then verified, simplified, and organized.

Significance and Claims
The paper claims to resolve an open problem in quantum graph theory by showing that the quantum chromatic number does not behave multiplicatively under categorical products, unlike the vector chromatic number and the Lovász theta number. The author emphasizes that their lower bounds rely solely on positivity in $C^{*}$ -algebras, making them applicable to all quantum models (tensor-product, spatial, approximate, and commuting-operator) without requiring trace conditions or dimension bounds.

The work highlights the gap between classical and quantum graph parameters, demonstrating that the "quantum advantage" in coloring can lead to structural behaviors distinct from classical coloring. The author modestly notes that they do not claim minimality for the size of the counterexamples and pose open questions regarding the smallest possible values for $c$ and the order of the base graph $F$ .

Technical Summary: A Counterexample to the Quantum Hedetniemi Conjecture

More like this