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)

Download

Share

COinS