A Quantum Framework for K Coloring of Graphs
Abstract
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 log2 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.
Related
- Quantum n-coloring is undecidable for every n ≥ 3
- Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
- Solving Graph Coloring Problems Using Feedback-Based Algorithm for Quantum Optimization
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
- Discrete Dirac equation on quantum graphs: A model of a Dirac particle in a branched lattice
BibTeX
@misc{sen2026quantum,
title = {{A Quantum Framework for K Coloring of Graphs}},
author = {Lord Sen and Shyamapada Mukherjee},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32348},
eprint = {2609.32348},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32348},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - A Quantum Framework for K Coloring of Graphs
AU - Lord Sen
AU - Shyamapada Mukherjee
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32348
UR - https://arxiv.org/abs/2609.32348
AB - 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.
ER -