Back to search

University of Central Florida

Quantum Graph Parameters

Abstract

dc:description.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.

Degree

thesis:*
Grantor dc:publisher
University of Central Florida

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Darbari Kozekanan, Parisa
Contributors dc:contributor
  • Leavens, Gary

Subjects

dc:subject × 3

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
CFE0009160; DP0026756

Chain of custody

source
Harvested from
Central Florida
Base URL
stars.library.ucf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Darbari Kozekanan, Parisa. Quantum Graph Parameters. University of Central Florida, https://stars.library.ucf.edu/etd2020/1189