Date of Award

6-2021

Document Type

Union College Only

Degree Name

Bachelor of Science

Department

Computer Science

First Advisor

Matthew Anderson

Keywords

Quantum Computing, Quantum Walk, Graph Theory

Abstract

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.

Download
Off-Campus Download

Share

COinS