Bounds of Quantum Mixing Processes via Controlled Walks

Simple item page
dc.contributor.advisorHøyer, Peter
dc.contributor.authorLi, Shang
dc.contributor.committeememberWoelfel, Philipp
dc.contributor.committeememberSwishchuk, Anatoliy V.
dc.contributor.committeememberHøyer, Peter
dc.date2020-11
dc.date.accessioned2020-04-30T21:32:11Z
dc.date.available2020-04-30T21:32:11Z
dc.date.issued2020-04-29
dc.description.abstractQuantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.en_US
dc.identifier.citationLi, S. (2020). Bounds of Quantum Mixing Processes via Controlled Walks (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/37751
dc.identifier.urihttp://hdl.handle.net/1880/111935
dc.language.isoengen_US
dc.publisher.facultyScienceen_US
dc.publisher.institutionUniversity of Calgaryen
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.en_US
dc.subjectQuantumen_US
dc.subjectQuantum Computingen_US
dc.subjectQuantum Algorithmen_US
dc.subjectQuantum Walksen_US
dc.subject.classificationComputer Scienceen_US
dc.titleBounds of Quantum Mixing Processes via Controlled Walksen_US
dc.typemaster thesisen_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorUniversity of Calgaryen_US
thesis.degree.nameMaster of Science (MSc)en_US
ucalgary.item.requestcopytrueen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ucalgary_2020_li_shang.pdf
Size:
2.5 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.62 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Open Theses and Dissertations