Quantum walk on two-dimensional torus and grid

Simple item page
dc.contributor.advisorHøyer, Peter
dc.contributor.authorKomeili, Mojtaba
dc.contributor.committeememberWoelfel, Philipp
dc.contributor.committeememberSwishchuk, Anatoliy V.
dc.date2018-11
dc.date.accessioned2018-05-30T20:07:48Z
dc.date.available2018-05-30T20:07:48Z
dc.date.issued2018-05-28
dc.description.abstractLet χ be a function that maps the vertices of a graph to zero or one. We want to find a vertex m, called a marked vertex, such that χ(m) = 1. Random walk is an algorithm for finding such a vertex. The measure of complexity for random walk is hitting time. There is a quantum algorithm that finds a marked vertex, and runs in the square root of the extended hitting time. For some configurations of marked vertices on certain graphs, the extended hitting time is asymptotically larger than the hitting time. This might cause the quantum algorithm for finding to be less efficient than a random walk. Two-dimensional torus and grid are canonical examples of such graphs. This thesis is about efficient quantum algorithms for finding a marked vertex on a two-dimensional torus. We prove the convexity of the extended hitting time, and provide a new upper bound on it. We show that, with a probability that is more than a constant, random walk on a torus is localized, and it is restricted to a sub-graph of the torus. From these observations, we introduce two algorithms that find a marked vertex on a torus. The complexity of these algorithms is in the order of the square root of the hitting time, up to logarithmic factors. They both start by finding an estimate to the hitting time. Using that, they estimate the size of a sub-graph that contains a marked vertex with more than a constant probability, and sample such a sub-graph. Our first algorithm finds a marked vertex on this sub-graph by using a quantum algorithm that runs in extended hitting time, and finds a marked vertex with probability at least a constant. Our second algorithm recursively runs the detection algorithm on cuts of the sub-graph, until reaching a constant sized sub-graph that contains a marked vertex. These algorithms are the first quantum algorithms that achieve close-to-quadratic speed-up in quantum walk on a two-dimensional torus, for all configurations of marked vertices.en_US
dc.identifier.citationKomeili, M. (2018). Quantum Walk on Two-dimensional Torus and Grid (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/31963en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/31963
dc.identifier.urihttp://hdl.handle.net/1880/106718
dc.language.isoeng
dc.publisher.facultyGraduate Studies
dc.publisher.facultyScience
dc.publisher.institutionUniversity of Calgaryen
dc.publisher.placeCalgaryen
dc.rightsUniversity 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.subjectQuantum Algorithm
dc.subjectQuantum Walk
dc.subjectRandom Walk
dc.subjectComputational Complexity
dc.subjectGraph
dc.subject.classificationComputer Scienceen_US
dc.titleQuantum walk on two-dimensional torus and grid
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameMaster of Science (MSc)
ucalgary.item.requestcopytrue
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ucalgary_2018_komeili_mojtaba.pdf
Size:
462.44 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.74 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Open Theses and Dissertations