{"id":{"repo_id":"calpoly","oai_identifier":"oai:digitalcommons.calpoly.edu:theses-3850"},"canonical_url":"https://search.ndltd.org/etd/calpoly/oai:digitalcommons.calpoly.edu:theses-3850","repository":{"repo_id":"calpoly","name":"Cal Poly","base_url":"https://digitalcommons.calpoly.edu/do/oai/"},"display":{"title":"Solving Chromatic Number with Quantum Search and Quantum Counting","abstract":"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.","abstract_html":"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&#x27;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.","abstract_has_math":false,"creators":["Lutze, David"],"institution":null,"degree_name":"MS in Computer Science","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Katharina Gillen","Computer Science","College of Engineering"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:12:03Z","subjects":["Grover Search","Chromatic Number","Quantum","Complexity","Quantum Algorithm","Quantum Information","Quantum Physics","Theory and Algorithms"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["10.15368/theses.2021.59"],"render_values":[{"text":"10.15368/theses.2021.59","href":"https://doi.org/10.15368/theses.2021.59","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.calpoly.edu/theses/2342","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.calpoly.edu/theses/2342","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.calpoly.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.calpoly.edu%3Atheses-3850","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Katharina Gillen","Computer Science","College of Engineering"]},{"key":"dc:creator","label":"Author","values":["Lutze, David"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2021-06-09T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2021-06-01T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS in Computer Science"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Grover Search","Chromatic Number","Quantum","Complexity","Quantum Algorithm","Quantum Information","Quantum Physics","Theory and Algorithms"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.calpoly.edu/theses/2342","10.15368/theses.2021.59"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Solving Chromatic Number with Quantum Search and Quantum Counting"]}]}],"canonical_facts":{"dc:contributor":["Katharina Gillen","Computer Science","College of Engineering"],"dc:creator":["Lutze, David"],"dc:date.available":["2021-06-09T07:00:00Z"],"dc:date.created":["2021-06-01T07:00:00Z"],"dc:description.abstract":["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."],"dc:identifier":["https://digitalcommons.calpoly.edu/theses/2342","10.15368/theses.2021.59"],"dc:subject":["Grover Search","Chromatic Number","Quantum","Complexity","Quantum Algorithm","Quantum Information","Quantum Physics","Theory and Algorithms"],"dc:title":["Solving Chromatic Number with Quantum Search and Quantum Counting"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["MS in Computer Science"]},"updated_at":"2026-11-19T07:12:03Z"}