Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physics
Solving Chromatic Number With Quantum Search And Quantum Counting, David Lutze
Solving Chromatic Number With Quantum Search And Quantum Counting, David Lutze
Master's Theses
This thesis presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2n/2n2(log2n)2). This is an improvement over the best known algorithm, with a run time of 2nnO(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which 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 …