Høyer, PeterYu, Zhan2021-11-012021-11-012021-10-29Yu, 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.http://hdl.handle.net/1880/114090The 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.engUniversity 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.Quantum walkRandom walkQuantum algorithmGraphEducation--MathematicsPhysicsComputer Sciencemaster thesis10.11575/PRISM/39369