For a N nodes graph, the complexity of the proposed method, called NK-method, is O (N 2) in number of qubits and O (N 4) in number of gates. It works for any K, but needs N 2 − N K + 1 qubits (and N K + 1 classical bits). As this number is quite high, we also propose a Q-method that requires significantly less qubits, but whose quantum circuit is far more complicated to build when K increases. For the NK-method we give a general Qiskit code that builds and simulates the quantum circuit. For the Q-method we just give a code for the 3-coloring. In these codes we use only gates whose unitary matrices are real. These codes can find all solutions that require at most K colours.
For a N nodes graph, the complexity of the proposed method, called NK-method, is O (N 2) in number of qubits and O (N 4) in number of gates. It works for any K, but needs N 2 − N K + 1 qubits (and N K + 1 classical bits). As this number is quite high, we also propose a Q-method that requires significantly less qubits, but whose quantum circuit is far more complicated to build when K increases. For the NK-method we give a general Qiskit code that builds and simulates the quantum circuit. For the Q-method we just give a code for the 3-coloring. In these codes we use only gates whose unitary matrices are real. These codes can find all solutions that require at most K colours.
Fundamentals of quantum computing are first introduced, specifically those necessary to understand the detailed algorithm later on, including classical concepts such as qubits, Poincaré-Bloch sphere, quantum gates, circuits, superposition, entanglement, and measurement. Once binary encodings have been performed (see Chapter 3) and with these elements, it is then relatively easy to design a quantum algorithm for searching for an optimal coloring. One such algorithm, the NK method, is detailed, based on the generation of so-called W quantum states, complemented by Grover's amplification-diffusion technique. In the absence of a real quantum computer, examples are treated through simulations coded in Qiskit language, with explicit representations of the constructed quantum circuits. They are necessarily of small size, but since the algorithm's complexity in terms of the number of nodes and colors is polynomial of low degree, it can, in principle, handle less trivial problems.
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 KN to K2N+m 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 δCq=89N2−83m2−43Nm−4N+4m 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.9575N) to O(1.9575(2N+m)) upon one symmetric reduction of graphs symmetric about an axis passing through m nodes and similarly for others cases.
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.
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.
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 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.