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:2609.32348 · International Conference on Computational Intelligence and Communication Networks (CICN)

A Quantum Framework for K Coloring of Graphs

Lord Sen, Shyamapada Mukherjee

quant-phSubmitted Sep 26, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

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 \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.

Related papers

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

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-Classical Approach to Solve the Graph Colouring Problem with Minimum Colours

Prem Shanker Dwivedi, Amit Biswas, Indu Dohare

Abstract Graph colouring with minimum colours 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 colouring problem with the minimum number of colours. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for exponential speed up 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 colouring problem with guaranteed correctness. The proposed method is inspired by Grover’s quantum search algorithm, the Clifford circuit, and the classical binary search algorithm. Here, Grover’s algorithm helps to achieve a quadratic speed up, Clifford circuit helps to mitigate the errors, and binary search helps to find the chromatic number with guaranteed correctness in polynomial time. We also conducted several experiments to evaluate the proposed method's performance and correctness, and the experimental results corroborate our claims regarding the proposed method. Additionally, a mathematical analysis is performed to assess its time and qubit complexities, and to compare its efficiency with existing methods.

•Oct 17, 2025•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

Circuit Design for K-coloring Problem and its Implementation on Near-term Quantum Devices

Amit Saha, Debasri Saha, Amlan Chakrabarti

Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.

arXiv:2009.06073•IEEE International Symposium on Smart Electronic Systems (iSES)•Dec 1, 2020•12 citations

Grover Algorithm-based Quantum Scheduling Framework for Constrained Graph Coloring

Lutfiana Sausan, Hyunsoo Lee

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.

Journal of Korean Institute of Industrial Engineers•Dec 15, 2025•0 citations
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.
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.
Abstract Graph colouring with minimum colours 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 colouring problem with the minimum number of colours. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for exponential speed up 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 colouring problem with guaranteed correctness. The proposed method is inspired by Grover’s quantum search algorithm, the Clifford circuit, and the classical binary search algorithm. Here, Grover’s algorithm helps to achieve a quadratic speed up, Clifford circuit helps to mitigate the errors, and binary search helps to find the chromatic number with guaranteed correctness in polynomial time. We also conducted several experiments to evaluate the proposed method's performance and correctness, and the experimental results corroborate our claims regarding the proposed method. Additionally, a mathematical analysis is performed to assess its time and qubit complexities, and to compare its efficiency with existing methods.
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.
Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.
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.