FYI: Colloquium of Dept. of Mathematical Sciences.

Quantum walks on graphs.

Chris Godsil

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada

2016/11/17 Thu 4:15PM-5:15PM

A quantum walk is a (rather imperfect analog) of a random walk on a graph. They can be viewed as gadgets that might play a role in quantum computers, and have been used to produce algorithms that outperform corresponding classical procedures. Physical questions about these walks lead to problems in spectral graph theory, and they also provide interesting new graph invariants. In my talk I will present some of the background, and some of the many open problems that they have given rise to.