Quantum Algorithms for Memoryless Search and Perfect Matching
Date
2023-07
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this thesis, we present two new quantum algorithms for graph problems. The first algorithm we give is a memoryless walk that can find a unique marked vertex on a two-dimensional grid. Our walk is based on a construction proposed by Falk, which tessellates the grid with squares of size 2 × 2. Our walk uses minimal memory, O(sqrt(N logN)) applications of the walk operator, and outputs the marked vertex with vanishing error probability. To accomplish this, we apply a selfloop to the marked vertex—a technique we adapt from interpolated walks. We prove that with our explicit choice of selfloop weight, this forces the action of the walk asymptotically into a single rotational space. We characterize this space and as a result, show that our memoryless walk produces the marked vertex with a success probability asymptotically approaching one. Our second algorithm decides whether a graph contains a perfect matching. This is the first quantum algorithm based on the algebraic characterization by Tutte, which reduces the problem of detecting perfect matchings to deciding whether a matrix has nonzero determinant. The key part of our algorithm is a new span program that can decide whether a matrix is singular. Our span program has a simple structure and its witness size matches that of a related span program by Belovs for matrix rank-finding, up to a constant factor. Using a transformation given by Reichardt, our span program can be compiled into a quantum algorithm, which we use as a subroutine in our algorithm to detect perfect matchings. We also show that there are families of graphs for which our perfect matching detection algorithm may have exponential query complexity. These graphs could be a useful tool in determining the tight quantum query complexity of the perfect matching detection problem, which remains an open problem.
Description
Keywords
Quantum, Algorithms, Graph theory
Citation
Leahy, J. (2023). Quantum algorithms for memoryless search and perfect matching (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.