A Quantum-Classical Approach to Solve the Graph Colouring Problem with Minimum Colours

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.