Date of Award
Union College Only
Bachelor of Science
Quantum Computing, Quantum Walk, Graph Theory
This research looked at the relationship between the expansion properties of a regular graph and the convergence time of a discrete-time quantum walk. Expander graphs, measured by their expansion parameters, exhibit high connectivity, while still being fairly sparse. Typically, a quantum walk on an arbitrary graph will converge on the target quadratically faster than with a classical random walk. It makes sense that the better of an expander a graph is, the faster the hitting time of a quantum walk will be. Data was collected by generating random d-regular graphs of different sizes and degrees, calculating their expansion coefficient, and then running a simulated quantum walk on the generated graphs to find the convergence time of a quantum walk. We found that as the spectral gap increased for graphs of a fixed size, the hitting time decreased proportionally, similar to a classical walk, while the maximum measurement probability increased. However, for randomly generated graphs of fixed size and degree, no dependence on the calculated expansion parameter was measured.
Bergh, Jasper, "Quantum Walks on Expander Graphs" (2021). Honors Theses. 2428.