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 be framed as NP-Hard problems, so any speed-up in the solution of these problems is highly sought after. A bulk of this thesis consists of a review of the underlying principles of quantum mechanics and quantum computing, building to the Quantum Search and Quantum Counting algorithms. The review is written with the assumption that the reader has no prior knowledge on quantum computing. This culminates with a presentation of algorithms for generating the quantum circuits required to solve K-Coloring and Chromatic Number.
| Identifer | oai:union.ndltd.org:CALPOLY/oai:digitalcommons.calpoly.edu:theses-3850 |
| Date | 01 June 2021 |
| Creators | Lutze, David |
| Publisher | DigitalCommons@CalPoly |
| Source Sets | California Polytechnic State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Master's Theses |
Page generated in 0.0018 seconds