Southwest Quantum Information and Technology

Obtaining Fastest Known Solution of Chromatic Number With Quantum Search and Quantum Counting

Presenting Author: David Lutze, California Polytechnic State University
Contributing Author(s): Katharina Gillen

Graphs consist of vertices connected by edges. Graphs can be used to model a variety of real world problems such as scheduling, route planning, and data transformation. K-Coloring is a graph problem where the solution is coloring all vertices such that no adjacent vertex is the same color. Chromatic Number’s solution is the smallest possible number of colors that can solve K-Coloring. This work presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2^(n/2)n^2(log2n)^2). This is an improvement over the best known algorithm, with a run time of 2^nn^O(1) [1]. This algorithm uses the Quantum Search algorithm, and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, and is an optimization variant of the NP-Complete problem K-Coloring. NP-Hard and NP-Complete problems are computationally expensive to solve. Any NP-Complete problem can be transformed into any other NP-Complete problem. The solution of Chromatic Number builds off a solution of the K-Coloring. As many NP-Hard problems are optimization variants of NP-Complete problems, this solution of Chromatic Number suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can be framed as NP-Hard problems, so any speed-up in the solution of these problems is widely beneficial. [1] DOI. 10.1137/070683933

Read this article online: https://digitalcommons.calpoly.edu/theses/2342/

(Session 5 : Thursday from 5:00 pm - 7:00 pm)