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.