Quantum Walks on Expander Graphs

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.

Union College Schaffer Library Digital Projects

Union College Schaffer Library Special Collections, 807 Union St., Schenectady, NY 12308; 518-388-6620; https://www.union.edu/schaffer-library