Many industrial optimization tasks can be modeled as graph coloring, where adjacent vertices must have different colors. This NP-hard problem is challenging for large graphs. We present a quantum encoding requiring qubits that scale logarithmically with the number of colors and linearly with vertices. Using adiabatic evolution with a novel mixer Hamiltonian and vertex terms, we compute the chromatic number and demonstrate robustness by solving constrained truck loading problems.
Many industrial optimization tasks can be modeled as graph coloring, where adjacent vertices must have different colors. This NP-hard problem is challenging for large graphs. We present a quantum encoding requiring qubits that scale logarithmically with the number of colors and linearly with vertices. Using adiabatic evolution with a novel mixer Hamiltonian and vertex terms, we compute the chromatic number and demonstrate robustness by solving constrained truck loading problems.
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(Nlog2K), 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.
Graph coloring is a well-known combinatorial optimization problem with broad applications in network security, scheduling, and register allocation. Being an NP-hard problem, exact solutions for large instances are computationally infeasible, calling for other solution strategies. In this study, parameterized and approximation methods to tackle the graph coloring problem are investigated. While approximation algorithms yield near-optimal solutions with theoretical guarantees of performance that are well-suited for large-scale applications, parameterized algorithms utilize graph-specific structural properties to manage constrained instances efficiently. We examine the trade-offs in these approaches, highlighting their strengths and weaknesses. In addition, we introduce a hybrid approach that combines both parameterized and approximation methods to best optimize computational resources and balance accuracy versus feasibility. Furthermore, we discuss the newly realized potential of quantum computing—specifically quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA)—to speed up graph coloring by leveraging quantum parallelism and state superposition. Such quantum-based techniques represent a promising line of attack for breaking up large and hard instances that overwhelm classical approaches. Future research will aim to tighten approximation guarantees, create quantum-augmented hybrid models, and test theoretical results against real-world datasets.
Abstract Graph coloring with minimum colors is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph coloring problem with the minimum number of colors. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for speedup on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum–classical method for solving the graph coloring problem and finding the chromatic number of a graph with guaranteed correctness, and also reduces the time and qubit complexities. The proposed method is inspired by Randomized Grover’s search algorithm, and the classical binary search algorithm. Here, Randomized Grover’s search algorithm provides quadratic speedup and this algorithm is useful in real situations when the number of solutions is not known in advance in contrast to the Grover’s search algorithm. The binary search algorithm helps to achieve logarithmic speedup, which reduces overall complexity. The experimental results strongly validate our claims and demonstrate the superiority of the approach. Furthermore, a comprehensive mathematical analysis is carried out to examine its complexities, as well as to compare its computational efficiency with existing methods.
Quantum computing holds significant promise for solving NP-hard combinatorial problems by leveraging quantum properties such as superposition, entanglement, and interference. In this study, we apply Grover’s algorithm to a constrained scheduling problem modeled as a graph coloring task with an added complexity: ensuring that the total processing time of all jobs assigned to a machine does not exceed its capacity. This additional constraint increases the problem’s difficulty beyond traditional graph coloring. Our proposed quantum framework demonstrates the ability to generate valid schedules that satisfy both coloring and capacity constraint, highlighting the practical potential of quantum computing for addressing complex scheduling challenges.
In the era of Noisy Intermediate Scale Quantum (NISQ) computing, available quantum resources are limited. Many NP-hard problems can be efficiently addressed using hybrid classical and quantum computational methods. This paper proposes a hybrid variational quantum algorithm designed to solve the k-coloring problem of graph vertices. The hybrid classical and quantum algorithms primarily partition the graph into multiple subgraphs through hierarchical techniques. The Quantum Approximate Optimization Algorithm (QAOA) is employed to determine the coloring within the subgraphs, while a classical greedy algorithm is utilized to find the coloring of the interaction graph. Fixed coloring is applied to the interaction graph, and feedback is provided to correct any conflicting colorings within the subgraphs. The merging process into the original graph is iteratively optimized to resolve any arising conflicts. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve k-coloring of arbitrary graph vertices. Through experimental analysis, we demonstrate the effectiveness of the algorithm, highlighting the rapid convergence of conflict evolution and the fact that iterative optimization allows the classical algorithm to approximate the number of colorings. Finally, we apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.
Genetic algorithms (GA) are computational methods for solving optimization problems inspired by natural selection. Because we can simulate the quantum circuits that implement GA in different highly configurable noise models and even run GA on actual quantum computers, we can analyze this class of heuristic methods in the quantum context for NP-hard problems. This paper proposes an instantiation of the Reduced Quantum Genetic Algorithm (RQGA) that solves the NP-hard graph coloring problem in O(N 1/2 ). The proposed implementation solves both vertex and edge coloring and can also determine the chromatic number ( i.e ., the minimum number of colors required to color the graph). We examine the results, analyze the algorithm convergence, and measure the algorithm's performance using the Qiskit simulation environment. Our Reduced Quantum Genetic Algorithm (RQGA) circuit implementation and the graph coloring results show that quantum heuristics can tackle complex computational problems more efficiently than their conventional counterparts.