Title: Quantum walks on regular graphs
| Speaker: | Krystal Guo |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
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 disprove this conjecture; the point graphs of the two generalized quadrangles of order (5,25) are not distinguished by this routine. 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. This is joint work with Chris Godsil and Tor Myklebust.