Tutte Colloquium - Krystal Guo

Title: Quantum walks on regular graphs

Abstract:

A quantum walk is a quantum process on a graph, which can be
used to implement a universal model of quantum computation. In this
talk, we will discuss discrete-time quantum walks. Emms, Hancock,
Severini and Wilson proposed a graph isomorphism routine for the class
of strongly regular graphs, based on the spectrum of a matrix related
to the discrete-time quantum walk. We give counterexamples to this
conjecture. Another matrix related to the discrete-time quantum walk
has been independently studied as the Bass-Hashimoto edge adjacency
operator, in the context of the Ihara zeta function of graphs. We find
its spectrum for the class of regular graphs. We will also discuss a
result about the cycle space of line digraphs of graphs, which is
motivated by the previous problems.