Quantum Algorithms for Memoryless Search and Perfect Matching
| dc.contributor.advisor | Høyer, Peter | |
| dc.contributor.author | Leahy, Janet | |
| dc.contributor.committeemember | Scheidler, Renate | |
| dc.contributor.committeemember | Feder, David | |
| dc.date | 2023-11 | |
| dc.date.accessioned | 2023-07-17T16:20:22Z | |
| dc.date.available | 2023-07-17T16:20:22Z | |
| dc.date.issued | 2023-07 | |
| dc.description.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. | |
| dc.identifier.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. | |
| dc.identifier.uri | https://hdl.handle.net/1880/116736 | |
| dc.identifier.uri | https://dx.doi.org/10.11575/PRISM/41578 | |
| dc.language.iso | en | |
| dc.publisher.faculty | Graduate Studies | |
| dc.publisher.institution | University of Calgary | |
| dc.rights | University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission. | |
| dc.subject | Quantum | |
| dc.subject | Algorithms | |
| dc.subject | Graph theory | |
| dc.subject.classification | Computer Science | |
| dc.title | Quantum Algorithms for Memoryless Search and Perfect Matching | |
| dc.type | master thesis | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | University of Calgary | |
| thesis.degree.name | Master of Science (MSc) | |
| ucalgary.thesis.accesssetbystudent | I do not require a thesis withhold – my thesis will have open access and can be viewed and downloaded publicly as soon as possible. |