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

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

Christian Bo Kidmose-Frederiksen, Alfred Leth Nielsen

quant-phmath.COSubmitted Oct 4, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

The quantum $n$-coloring problem, given graph $G$, asks whether there exists a perfect quantum strategy for the $n$-coloring game of $G$. Previously it was known that quantum $n$-coloring is undecidable only for $n=3$. We extend this to all $n\geq 3$ with one elementary reduction. Letting $G'=(G\square K_3)\lor K_{n-3}$, we show that $G$ is quantum $3$-colorable if and only if $G'$ is quantum $n$-colorable.

AI Summary

Quantum $n$-coloring asks whether a graph admits a perfect quantum strategy for its $n$-coloring game, equivalently a finite-dimensional assignment of projections satisfying completeness and edge orthogonality. Undecidability was previously known for $n=3$, while the cases of fixed $n\ge4$ remained open. This paper establishes undecidability for every fixed $n\ge3$; quantum $1$- and $2$-colorability coincide with their classical counterparts and are decidable. The result follows from the polynomial-time reduction $G'=(G\square K_3)\vee K_{n-3}$, with $3|V(G)|+n-3$ vertices, and the equivalence $G\to_q K_3$ if and only if $G'\to_q K_n$. The forward construction cyclically permutes a quantum $3$-coloring across each three-vertex fibre and assigns separate colors to the added clique. Conversely, each fibre together with the added clique forms an $n$-clique. Completeness and orthogonality force the three projections associated with any fixed color in a fibre to sum to a projection independent of the fibre. Choosing a nonzero such projection and restricting to its range recovers a quantum $3$-coloring, in dimension no larger than the original strategy dimension. The reduction also applies to the commuting-operator model. The paper notes independent proofs of the undecidability result and a separate gapped version; its own argument concerns exact perfect-strategy existence. It does not resolve the general fixed-target quantum $H$-coloring problem, and states the conjecture that this problem is undecidable for every non-bipartite $H$.

No sign of AI-generated text

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

Related papers

A Grover Search-Based Algorithm for the List Coloring Problem

Sayan Mukherjee

Graph coloring is a computationally difficult problem, and currently the best known classical algorithm for$k$-coloring of graphs on$n$vertices has runtimes$\Omega (2^n)$for$k\geq 5$. The list coloring problem asks the following more general question: given alistof available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based on Grover search 12 to quadratically speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases, where the lists and graphs considered are arbitrary in nature.

arXiv:2108.09061•IEEE Transactions on Quantum Engineering•Jan 1, 2022•26 citations

Algebras, Synchronous Games and Chromatic Numbers of Graphs

J. William Helton, Kyle Meyer, Vern I. Paulsen +1 more

We associate to each synchronous game an algebra whose representations determine if the game has a perfect deterministic strategy, perfect quantum strategy or one of several other perfect strategies. when applied to the graph coloring game, this leads to characterizations in terms of properties of an algebra of various quantum chromatic numbers that have been studied in the literature. This allows us to develop a correspondence between various chromatic numbers of a graph and ideals in this algebra which can then be approached via various Grobner basis methods.

arXiv:1703.00960•Mar 2, 2017•44 citations

Quantum Perfect Matchings

David Cui, Laura Mančinska, Seyed Sajjad Nezhadi +1 more

Abstract We investigate quantum and nonsignaling generalizations of perfect matchings in graphs using nonlocal games. Specifically, we introduce nonlocal games that test for L-perfect matchings in bipartite graphs, perfect matchings in general graphs and hypergraphs, and fractional perfect matchings. Our definitions come from the fact that these games are classical property tests for the corresponding matching conditions. We use the existence of perfect quantum and nonsignaling strategies for these games to define quantum and nonsignaling versions of perfect matchings. Finally, we provide characterizations of when graphs exhibit these extended properties: For nonsignaling matchings, we give a complete combinatorial characterization. In particular, a graph has a nonsignaling perfect matching if and only if it admits a fractional perfect matching that has bounded value on triangles. In bipartite graphs, the nonsignaling L-perfect matching property is achieved exactly when the left component of the graph can be split into two disjoint subgraphs: one with a classical L-perfect matching and another with left-degree 2. In the quantum setting, we show that complete graphs $$K_n$$ K n with odd $$n \ge 7$$ n ≥ 7 have quantum perfect matchings. We prove that a graph has a quantum perfect matching if and only if the quantum independence number of its line graph is maximal, extending a classical relationship between perfect matchings and line graph independence numbers. For bipartite graphs, we establish that the L-perfect matching game does not exhibit quantum pseudotelepathy, but we characterize the quantum advantage for complete bipartite graphs $$K_{n,2}$$ K n , 2 . Additionally, we prove that deciding quantum perfect matchings in hypergraphs is undecidable and leaves open the question of its complexity in graphs.

arXiv:2502.05136•Annales Henri Poincaré•Oct 14, 2025•3 citations

A Quantum Framework for K Coloring of Graphs

Lord Sen, Shyamapada Mukherjee

Graph coloring is a well-known NP-complete problem with applications in scheduling, register allocation, frequency assignment, and network optimization. Quantum computing offers the potential for polynomial or even super-polynomial speedups in certain problem instances, yet practical quantum graph coloring methods must carefully balance qubit resources, circuit depth, and constraint enforcement. We proposed a solver agnostic quantum framework for $K$-coloring. Along with a novel encoding and efficient constraint implementation for its exact coloring exploiting Grover search and almost optimal coloring by the Quantum Approximate Optimization Algorithm \emph{(QAOA)}, and \emph{Quantum Annealing}. Unlike using $O(NK)$ qubits as in \emph{SOTA}, we reduced the qubit requirements to $O(N \log_2 K)$, along with optimized comparator circuits enforcing adjacency constraints. Further symmetry-based graph reduction is incorporated as an optional preprocessing step to further reduce the instance size before quantum execution.

quant-pharXiv:2609.32348•International Conference on Computational Intelligence and Communication Networks (CICN)•Sep 29, 2026•0 citations

Symmetric Reduction Techniques for Quantum Graph Colouring

Lord Sen, Shyamapada Mukherjee

This paper introduces an efficient quantum computing method for reducing special graphs in the context of the graph coloring problem. The special graphs considered include both symmetric and non-symmetric graphs where the axis passes through nodes only, edges only, and both together. The presented method reduces the number of coloring matrices, which is important for realization of the number of quantum states required, from $K^{N}$ to $K^{\frac{N+m}{2}}$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes, where $K$ is the number of colours required and \emph{N} being total number of nodes. Similarly for other types also, the number of quantum states is reduced. The complexity in the number of qubits has been reduced by $δC_q= \frac{9N^2}{8}-\frac{3m^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}$ upon one symmetric reduction of graphs, symmetric about an axis passing through $m$ nodes and other types as presented in the paper. Additionally, the number of gates and number of iterations are reduced massively compared to state-of-the-art quantum algorithms. Like for a graph with 20 nodes and symmetric line passing through 2 nodes, the number of iterations decreased from 5157 to 67. Therefore, the procedure presented for solving the graph coloring problem now requires a significantly reduced number of qubits compared to before. The run time of the proposed algorithm for these special type of graphs are reduced from $O(1.9575^{N})$ to $O(1.9575^{(\frac{N+m}{2})})$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes and similarly for others cases.

arXiv:2510.16784•Oct 19, 2025•2 citations

The quantum-to-classical graph homomorphism game

Michael Brannan, Priyanga Ganesan, Samuel J. Harris

Motivated by non-local games and quantum coloring problems, we introduce a graph homomorphism game between quantum graphs and classical graphs. This game is naturally cast as a “quantum–classical game,” that is, a non-local game of two players involving quantum questions and classical answers. This game generalizes the graph homomorphism game between classical graphs. We show that winning strategies in the various quantum models for the game is an analog of the notion of non-commutative graph homomorphisms due to Stahlke [IEEE Trans. Inf. Theory 62(1), 554–577 (2016)]. Moreover, we present a game algebra in this context that generalizes the game algebra for graph homomorphisms given by Helton et al. [New York J. Math. 25, 328–361 (2019)]. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the four coloring game for a quantum graph is always non-trivial, extending a result of Helton et al. [New York J. Math. 25, 328–361 (2019)].

arXiv:2009.07229•Journal of Mathematical Physics•Nov 1, 2022•28 citations
The quantum nnn-coloring problem, given graph GGG, asks whether there exists a perfect quantum strategy for the nnn-coloring game of GGG. Previously it was known that quantum nnn-coloring is undecidable only for n=3n=3n=3. We extend this to all n≥3n\geq 3n≥3 with one elementary reduction. Letting G′=(G□K3)∨Kn−3G'=(G\square K_3)\lor K_{n-3}G′=(G□K3​)∨Kn−3​, we show that GGG is quantum 333-colorable if and only if G′G'G′ is quantum nnn-colorable.
Quantum nnn-coloring asks whether a graph admits a perfect quantum strategy for its nnn-coloring game, equivalently a finite-dimensional assignment of projections satisfying completeness and edge orthogonality. Undecidability was previously known for n=3n=3n=3, while the cases of fixed n≥4n\ge4n≥4 remained open. This paper establishes undecidability for every fixed n≥3n\ge3n≥3; quantum 111- and 222-colorability coincide with their classical counterparts and are decidable.
The result follows from the polynomial-time reduction G′=(G□K3)∨Kn−3G'=(G\square K_3)\vee K_{n-3}G′=(G□K3​)∨Kn−3​, with 3∣V(G)∣+n−33|V(G)|+n-33∣V(G)∣+n−3 vertices, and the equivalence G→qK3G\to_q K_3G→q​K3​ if and only if G′→qKnG'\to_q K_nG′→q​Kn​. The forward construction cyclically permutes a quantum 333-coloring across each three-vertex fibre and assigns separate colors to the added clique. Conversely, each fibre together with the added clique forms an nnn-clique. Completeness and orthogonality force the three projections associated with any fixed color in a fibre to sum to a projection independent of the fibre. Choosing a nonzero such projection and restricting to its range recovers a quantum 333-coloring, in dimension no larger than the original strategy dimension.
The reduction also applies to the commuting-operator model. The paper notes independent proofs of the undecidability result and a separate gapped version; its own argument concerns exact perfect-strategy existence. It does not resolve the general fixed-target quantum HHH-coloring problem, and states the conjecture that this problem is undecidable for every non-bipartite HHH.
Graph coloring is a computationally difficult problem, and currently the best known classical algorithm forkkk-coloring of graphs onnnnvertices has runtimesΩ(2n)\Omega (2^n)Ω(2n)fork≥5k\geq 5k≥5. The list coloring problem asks the following more general question: given alistof available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based on Grover search 12 to quadratically speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases, where the lists and graphs considered are arbitrary in nature.
We associate to each synchronous game an algebra whose representations determine if the game has a perfect deterministic strategy, perfect quantum strategy or one of several other perfect strategies. when applied to the graph coloring game, this leads to characterizations in terms of properties of an algebra of various quantum chromatic numbers that have been studied in the literature. This allows us to develop a correspondence between various chromatic numbers of a graph and ideals in this algebra which can then be approached via various Grobner basis methods.
Abstract We investigate quantum and nonsignaling generalizations of perfect matchings in graphs using nonlocal games. Specifically, we introduce nonlocal games that test for L-perfect matchings in bipartite graphs, perfect matchings in general graphs and hypergraphs, and fractional perfect matchings. Our definitions come from the fact that these games are classical property tests for the corresponding matching conditions. We use the existence of perfect quantum and nonsignaling strategies for these games to define quantum and nonsignaling versions of perfect matchings. Finally, we provide characterizations of when graphs exhibit these extended properties: For nonsignaling matchings, we give a complete combinatorial characterization. In particular, a graph has a nonsignaling perfect matching if and only if it admits a fractional perfect matching that has bounded value on triangles. In bipartite graphs, the nonsignaling L-perfect matching property is achieved exactly when the left component of the graph can be split into two disjoint subgraphs: one with a classical L-perfect matching and another with left-degree 2. In the quantum setting, we show that complete graphs KnK_nKn​ K n with odd n≥7n \ge 7n≥7 n ≥ 7 have quantum perfect matchings. We prove that a graph has a quantum perfect matching if and only if the quantum independence number of its line graph is maximal, extending a classical relationship between perfect matchings and line graph independence numbers. For bipartite graphs, we establish that the L-perfect matching game does not exhibit quantum pseudotelepathy, but we characterize the quantum advantage for complete bipartite graphs Kn,2K_{n,2}Kn,2​ K n , 2 . Additionally, we prove that deciding quantum perfect matchings in hypergraphs is undecidable and leaves open the question of its complexity in graphs.
Graph coloring is a well-known NP-complete problem with applications in scheduling, register allocation, frequency assignment, and network optimization. Quantum computing offers the potential for polynomial or even super-polynomial speedups in certain problem instances, yet practical quantum graph coloring methods must carefully balance qubit resources, circuit depth, and constraint enforcement. We proposed a solver agnostic quantum framework for KKK-coloring. Along with a novel encoding and efficient constraint implementation for its exact coloring exploiting Grover search and almost optimal coloring by the Quantum Approximate Optimization Algorithm \emph{(QAOA)}, and \emph{Quantum Annealing}. Unlike using O(NK)O(NK)O(NK) qubits as in \emph{SOTA}, we reduced the qubit requirements to O(Nlog⁡2K)O(N \log_2 K)O(Nlog2​K), along with optimized comparator circuits enforcing adjacency constraints. Further symmetry-based graph reduction is incorporated as an optional preprocessing step to further reduce the instance size before quantum execution.
This paper introduces an efficient quantum computing method for reducing special graphs in the context of the graph coloring problem. The special graphs considered include both symmetric and non-symmetric graphs where the axis passes through nodes only, edges only, and both together. The presented method reduces the number of coloring matrices, which is important for realization of the number of quantum states required, from KNK^{N}KN to KN+m2K^{\frac{N+m}{2}}K2N+m​ upon one symmetric reduction of graphs symmetric about an axis passing through mmm nodes, where KKK is the number of colours required and \emph{N} being total number of nodes. Similarly for other types also, the number of quantum states is reduced. The complexity in the number of qubits has been reduced by δCq=9N28−3m28−3Nm4−N4+m4δC_q= \frac{9N^2}{8}-\frac{3m^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}δCq​=89N2​−83m2​−43Nm​−4N​+4m​ upon one symmetric reduction of graphs, symmetric about an axis passing through mmm nodes and other types as presented in the paper. Additionally, the number of gates and number of iterations are reduced massively compared to state-of-the-art quantum algorithms. Like for a graph with 20 nodes and symmetric line passing through 2 nodes, the number of iterations decreased from 5157 to 67. Therefore, the procedure presented for solving the graph coloring problem now requires a significantly reduced number of qubits compared to before. The run time of the proposed algorithm for these special type of graphs are reduced from O(1.9575N)O(1.9575^{N})O(1.9575N) to O(1.9575(N+m2))O(1.9575^{(\frac{N+m}{2})})O(1.9575(2N+m​)) upon one symmetric reduction of graphs symmetric about an axis passing through mmm nodes and similarly for others cases.
Motivated by non-local games and quantum coloring problems, we introduce a graph homomorphism game between quantum graphs and classical graphs. This game is naturally cast as a “quantum–classical game,” that is, a non-local game of two players involving quantum questions and classical answers. This game generalizes the graph homomorphism game between classical graphs. We show that winning strategies in the various quantum models for the game is an analog of the notion of non-commutative graph homomorphisms due to Stahlke [IEEE Trans. Inf. Theory 62(1), 554–577 (2016)]. Moreover, we present a game algebra in this context that generalizes the game algebra for graph homomorphisms given by Helton et al. [New York J. Math. 25, 328–361 (2019)]. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the four coloring game for a quantum graph is always non-trivial, extending a result of Helton et al. [New York J. Math. 25, 328–361 (2019)].