Keywords

Quantum chromatic number; Graph algorithms; Quantum computing; Pattern matching; Time complexity

Abstract

This dissertation considers some of the advantages, and limits, of applying quantum computing to solve two important graph problems. The first is estimating a graph's quantum chromatic number. The quantum chromatic number is the minimum number of colors necessary in a two-player game where the players cannot communicate but share an entangled state and must convince a referee with probability one that they have a proper vertex coloring. We establish several spectral lower bounds for the quantum chromatic number. These lower bounds extend the well-known Hoffman lower bound for the classical chromatic number. The second is the Pattern Matching on Labeled Graphs Problem (PMLG). Here the objective is to match a string (called a pattern) P to a walk in an edge labeled graph G = (V, E). In addition to providing a new quantum algorithm for PMLG, this work establishes conditional lower bounds on the time complexity of any quantum algorithm for PMLG. These include a conditional lower bound based on the recently proposed NC-QSETH and a reduction from the Longest Common Subsequence Problem (LCS). For PMLG where substitutions are allowed to the pattern, our results demonstrate that (i) a quantum algorithm running in time O(|E|m1-ε + |E|1-εm) for any constant ε > 0 would provide an algorithm for LCS on two strings X and Y running in time Õ(|X||Y|1-ε + |X|1-ε|Y|), which is better than any known quantum algorithm for LCS, and (ii) a quantum algorithm running in time O(|E|m½-ε + |E|½-εm) would violate NC-QSETH. Results (i) and (ii) hold even when restricted to binary alphabets for P and the edge labels in G. Our quantum algorithm is for all versions of PMLG (exact, only substitutions, and substitutions/insertions/deletions) and runs in time Õ(√|V||E|· m), making it an improvement over the classical O(|E|m) time algorithm when the graph is non-sparse.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

2022

Semester

Summer

Advisor

Leavens, Gary

Degree

Doctor of Philosophy (Ph.D.)

College

College of Engineering and Computer Science

Department

Computer Science

Degree Program

Computer Science

Identifier

CFE0009160; DP0026756

URL

https://purls.library.ucf.edu/go/DP0026756

Language

English

Release Date

August 2022

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Subjects

Quantum graphs; Graph theory --Extremal problems; Quantum computing; Graph algorithms; Quantum theory--Computer programs

Download

Share

COinS
 

Accessibility Statement

This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.