Quantum Walks and Structured Searches on Free Groups and Networks

Abstract

Quantum walks have been utilized by many quantum algorithms which provide improved performance over their classical counterparts. Quantum search algorithms, the quantum analogues of spatial search algorithms, have been studied on a wide variety of structures. We study quantum walks and searches on the Cayley graphs of finitely-generated free groups. Return properties are analyzed via Green’s functions, and quantum searches are examined. Additionally, the stopping times and success rates of quantum searches on random networks are experimentally estimated.