⚛️ quantum physics

Quantum n-coloring is undecidable for every n $\ge$ 3

This paper proves that the quantum $n$ -coloring problem is undecidable for all integers $n \geq 3$ by establishing an elementary reduction that transforms the known undecidable case of $n=3$ into the general case.

Original authors: Christian Bo Kidmose-Frederiksen, Alfred Leth Nielsen

Published 2026-10-06

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Christian Bo Kidmose-Frederiksen, Alfred Leth Nielsen

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 quiet corners of mathematics and computer science, there exists a class of problems that ask a simple question: can a specific set of rules be followed without contradiction? One of the most famous of these is the graph coloring problem. Imagine a map where every region must be painted a color, but no two regions that share a border can have the same shade. For a long time, mathematicians knew that for maps with just two colors, the answer could be found quickly by a computer. However, once the number of available colors increases, the problem becomes vastly more complex. In the realm of quantum physics, where particles can exist in multiple states at once and share deep, invisible connections, this coloring game takes on a new form. Here, the "colors" are not just paint, but mathematical tools called projections that describe the state of a quantum system. The question shifts from whether a map can be colored with standard rules to whether a perfect strategy exists for a quantum version of the game. This distinction matters because it touches on the very limits of what can be computed. If a problem is undecidable, it means no computer, no matter how powerful or how much time it is given, can ever guarantee an answer.

For years, researchers knew that this quantum coloring game was impossible to solve for a specific case involving three colors. The mystery remained for any number of colors greater than three. A team of undergraduate students at the Technical University of Denmark has now closed that gap. They proved that the quantum coloring problem is undecidable for every number of colors starting from three and going up. Their work does not rely on complex simulations or unproven theories; it is a rigorous mathematical proof that extends a known impossibility to a whole new range of possibilities. By constructing a specific bridge between the three-color case and any higher number of colors, they showed that if a computer cannot solve the three-color version, it cannot solve any version with more colors either.

The researchers began with a graph, which is simply a collection of points connected by lines, representing the regions and borders of the coloring map. They then created a new, larger graph by combining the original one with a small, fixed structure and a complete group of points. This construction is a precise recipe that can be followed quickly by a computer. The core of their discovery lies in showing that the ability to color this new, larger graph with a specific number of colors is exactly the same as the ability to color the original small graph with just three colors. If the original graph can be solved using a quantum strategy for three colors, the new graph can be solved for the larger number. Conversely, if the new graph can be solved, the original must have been solvable for three colors. This creates a direct link, or a reduction, meaning that the difficulty of the larger problem is identical to the difficulty of the smaller one.

Since it was already established that the three-color quantum problem is undecidable, this link proves that the larger problems are undecidable as well. The students demonstrated that there is no algorithm that can look at a graph and a number of colors greater than three and definitively say whether a perfect quantum strategy exists. The proof works by showing that any attempt to solve the larger problem would essentially require solving the impossible three-color problem first. This result holds true whether the quantum system is finite or infinite, covering all standard models of quantum mechanics used in this field. The finding settles a question that had been open for some time, confirming that the barrier to computation is not just a quirk of the three-color case but a fundamental feature of the entire family of quantum coloring problems.

The implications of this work reach beyond the specific game of coloring. It suggests a broader pattern in the complexity of quantum systems. The authors note that while some specific types of quantum coloring problems are solvable, the general case for non-bipartite structures appears to be impossible to decide. They propose a conjecture that for any structure that is not a simple two-part division, the quantum coloring problem will likely be undecidable. This aligns with a known divide in classical mathematics, where problems are either easy or hard, but here the "hard" side has been shown to be truly unsolvable. The work stands as a clear demonstration that in the quantum world, the limits of computation are stricter than previously thought, and that for a vast array of scenarios, the answer to whether a perfect strategy exists is a question that no machine can ever answer.

Technical Summary: Quantum n-Coloring is Undecidable for Every n ≥ 3

Problem Statement
The paper addresses the decision problem of quantum n-coloring. Given a finite, simple, undirected graph $G$ , the problem asks whether there exists a "perfect quantum strategy" for the $n$ -coloring game of $G$ . In algebraic terms, this corresponds to determining if $G$ admits a quantum $n$ -coloring, defined as an assignment of projection operators $\{P_{u,i}\}_{i=1}^n$ in a finite-dimensional matrix algebra $C^{d \times d}$ to each vertex $u \in V(G)$ such that:

Completeness: For every vertex $u$ , $\sum_{i=1}^n P_{u,i} = I$ .
Orthogonality: For every edge $u \sim v$ and every color $i$ , $P_{u,i} P_{v,i} = 0$ .

Prior to this work, it was established that quantum 3-coloring is undecidable (via reductions from synchronous nonlocal games and Slofstra's linear-system games). However, the decidability status for all $n \geq 4$ remained an open question.

Methodology
The authors employ a many-one reduction to extend the known undecidability of quantum 3-coloring to all $n \geq 3$ . The core of the methodology is a specific graph transformation that maps an arbitrary graph $G$ to a new graph $G'$ such that $G$ is quantum 3-colorable if and only if $G'$ is quantum $n$ -colorable.

The transformation is defined as:
$G' := (G \square K_3) \vee K_{n-3}$
Where:

$\square$ denotes the Cartesian product. In $G \square K_3$ , every vertex $u \in V(G)$ is replaced by a "fibre" of three vertices $\{(u,1), (u,2), (u,3)\}$ .
$\vee$ denotes the join operation. The graph $G'$ is formed by taking the Cartesian product and joining it with a clique of size $n-3$ (vertices labeled $4, \dots, n$ ).

The authors prove the equivalence $G \xrightarrow{q} K_3 \iff G' \xrightarrow{q} K_n$ (Lemma 3.1) through two directions:

Forward Direction ( $\Rightarrow$ ): Given a quantum 3-coloring of $G$ , the authors construct a quantum $n$ -coloring of $G'$ . They utilize the existing projections for $G$ and shift indices modulo 3 to assign projections to the fibre vertices in $G'$ . The clique $K_{n-3}$ is assigned trivial projections (identity matrices for specific colors) to satisfy the constraints.
Backward Direction ( $\Leftarrow$ ): Given a quantum $n$ -coloring of $G'$ , the authors recover a quantum 3-coloring of $G$ . By analyzing the clique structure formed by the fibre of any vertex $v$ combined with the $K_{n-3}$ clique, they demonstrate that the sum of projections for the fibre vertices is independent of the specific vertex $v$ . They further prove that for at least one color $i^*$ , the "remainder" projection (associated with the clique $K_{n-3}$ ) is not the identity, allowing the restriction of the $n$ -coloring to a valid 3-coloring on a subspace.

Key Contributions and Results

Generalization of Undecidability: The primary result (Theorem 3.2) establishes that the quantum $n$ -coloring decision problem is undecidable for every fixed integer $n \geq 3$ .
Elementary Reduction: The paper provides a single, polynomial-time computable reduction that bridges the gap between the $n=3$ case and all higher $n$ . This resolves the open problem regarding $n \geq 4$ .
Robustness: The proof holds for both the standard finite-dimensional quantum model and the quantum commuting-operator model (where projections act on arbitrary, possibly infinite-dimensional Hilbert spaces).

Significance and Claims
The authors position this work as a definitive extension of previous results by Harris [9], Mančinska [4], and Culf [2]. The significance lies in closing the decidability gap for quantum coloring games.

The paper concludes by situating these results within the broader context of quantum homomorphisms. Since quantum $n$ -coloring is equivalent to the existence of a quantum homomorphism from $G$ to the complete graph $K_n$ , the authors propose a conjecture regarding the general complexity of quantum $H$ -coloring:

Conjecture 4.1: For every non-bipartite graph $H$ , quantum $H$ -coloring is undecidable.

The authors note that while the problem is decidable for bipartite $H$ (reducing to classical coloring) and undecidable for odd cycles, the general case for non-bipartite graphs remains an open area of research, with this paper serving as a foundational step toward a potential "Hell–Nešetřil dichotomy" in the quantum setting.

Technical Summary: Quantum n-Coloring is Undecidable for Every n ≥ 3

More like this