Quantum Walks on Arc-Transitive Graphs with Self-Loops
Date
2021-10-29
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each vertex in the graph. The lackadaisical quantum walk has been studied on cycles, n-dimensional tori, hypercubes, Johnson graphs, and other classes of vertex-transitive graphs. The results of numerical simulation show that lackadaisical quantum walks can find a unique marked vertex on these graphs with constant success probability quadratically faster than the random walk, and the optimal weight of the self-loops is ℓ = d/N where d is the degree of the vertices and N is the number of vertices. One common property of these classes of graphs is that they are locally arc-transitive.
In this thesis, we analytically prove that for any d-regular locally arc-transitive graph, by adding a self-loop of weight ℓ = d/N on each vertex, the lackadaisical quantum walk finds a unique marked vertex with probability at least a constant. Our proof establishes and uses a relationship between the lackadaisical quantum walk and the quantum interpolated walk that was introduced by Krovi, Magniez, Ozols, and Roland in 2015. Our result proves speculations and numerical findings of lackadaisical quantum walks in previous work.
Description
Keywords
Quantum walk, Random walk, Quantum algorithm, Graph
Citation
Yu, Z. (2021). Quantum Walks on Arc-Transitive Graphs with Self-Loops (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.