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

Journal of Korean Institute of Industrial Engineers

Grover Algorithm-based Quantum Scheduling Framework for Constrained Graph Coloring

Lutfiana Sausan, Hyunsoo Lee

Published Dec 15, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.7232/jkiie.2025.51.6.454

Related papers

A quantum–classical approach to solve the graph coloring problem with minimum colors

Prem Shanker Dwivedi, Abhinav Kumar, Amit Biswas +1 more

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.

Physica Scripta•Oct 9, 2026•0 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

Approximation Meets Quantum: A Parameterized Framework for Large-Scale Graph Coloring

Rahul Pitale, Kapil Tajane, Prashant Ahire +4 more

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.

Asian Conference on Innovation in Technology (ASIANCON)•Aug 22, 2025•0 citations

Quantum Based Grover's Algorithm and Graph Coloring in Unstructured Searches for Bit String Validation

S Vinodhkumar, P Pravin, Pradeep Kumar

Quantum computing based Grover's algorithm performs unstructured search problems in unsorted data to structured data in validating bit string through graph coloring. The quantum Grover's algorithm and graph theory was looked at in graph coloring. In graph coloring algorithm can be leveraged to validate coloring assignments for graph with arbitrary structures. It's accuracy and efficiency has been achieved by the iteration of square root (N) By adapting Grover's search mechanism, we aim to optimize the process of finding valid coloring in a graph, which is a crucial NP-complete problem in classical computation. This algorithm determines shortest node to see if the gates can be colored rightly for detect validation bit string. To get a validated a significant advantage of the hybrid classical-quantum approach reduces time complexity and exhaustive search. Grover's algorithm reduces the number of iterations needed for a solution, providing a quantum advantage in efficiency.

International Conference on Visual Analytics and Data Visualization (ICVADV)•Mar 4, 2025•10 citations

A Resource-Efficient Quantum Framework for Graph Coloring and Chromatic Number Estimation

Francesco Turro, Daniele Dragoni

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.

quant-pharXiv:2608.08694•Aug 11, 2026•0 citations

Solving Multi-Coloring Combinatorial Optimization Problems Using Hybrid Quantum Algorithms

Young-Hyun Oh, Hamed Mohammadbagherpoor, Patrick Dreher +3 more

The design of a good algorithm to solve NP-hard combinatorial approximation problems requires specific domain knowledge about the problems and often needs a trial-and-error problem solving approach. Graph coloring is one of the essential fields to provide an efficient solution for combinatorial applications such as flight scheduling, frequency allocation in networking, and register allocation. In particular, some optimization algorithms have been proposed to solve the multi-coloring graph problems but most of the cases a simple searching method would be the best approach to find an optimal solution for graph coloring problems. However, this naive approach can increase the computation cost exponentially as the graph size and the number of colors increase. To mitigate such intolerable overhead, we investigate the methods to take the advantages of quantum computing properties to find a solution for multi-coloring graph problems in polynomial time. We utilize the variational quantum eigensolver (VQE) technique and quantum approximate optimization algorithm (QAOA) to find solutions for three combinatorial applications by both transferring each problem model to the corresponding Ising model and by using the calculated Hamiltonian matrices. Our results demonstrate that VQE and QAOA algorithms can find one of the best solutions for each application. Therefore, our modeling approach with hybrid quantum algorithms can be applicable for combinatorial problems in various fields to find an optimal solution in polynomial time.

arXiv:1911.00595•Nov 1, 2019•12 citations
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.
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.
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.
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.
Quantum computing based Grover's algorithm performs unstructured search problems in unsorted data to structured data in validating bit string through graph coloring. The quantum Grover's algorithm and graph theory was looked at in graph coloring. In graph coloring algorithm can be leveraged to validate coloring assignments for graph with arbitrary structures. It's accuracy and efficiency has been achieved by the iteration of square root (N) By adapting Grover's search mechanism, we aim to optimize the process of finding valid coloring in a graph, which is a crucial NP-complete problem in classical computation. This algorithm determines shortest node to see if the gates can be colored rightly for detect validation bit string. To get a validated a significant advantage of the hybrid classical-quantum approach reduces time complexity and exhaustive search. Grover's algorithm reduces the number of iterations needed for a solution, providing a quantum advantage in efficiency.
The design of a good algorithm to solve NP-hard combinatorial approximation problems requires specific domain knowledge about the problems and often needs a trial-and-error problem solving approach. Graph coloring is one of the essential fields to provide an efficient solution for combinatorial applications such as flight scheduling, frequency allocation in networking, and register allocation. In particular, some optimization algorithms have been proposed to solve the multi-coloring graph problems but most of the cases a simple searching method would be the best approach to find an optimal solution for graph coloring problems. However, this naive approach can increase the computation cost exponentially as the graph size and the number of colors increase. To mitigate such intolerable overhead, we investigate the methods to take the advantages of quantum computing properties to find a solution for multi-coloring graph problems in polynomial time. We utilize the variational quantum eigensolver (VQE) technique and quantum approximate optimization algorithm (QAOA) to find solutions for three combinatorial applications by both transferring each problem model to the corresponding Ising model and by using the calculated Hamiltonian matrices. Our results demonstrate that VQE and QAOA algorithms can find one of the best solutions for each application. Therefore, our modeling approach with hybrid quantum algorithms can be applicable for combinatorial problems in various fields to find an optimal solution in polynomial time.