University of Waterloo, Canada
- In probability theory a discrete random walk is often defined by the powers of a stochastic matrix, a non-negative matrix with each row summing to 1. In quantum computing a discrete walk is specified by the powers of a unitary matrix. One difficulty is that to be useful, the unitary matrix must satisfy some structural conditions, and in practice this often means that the walk is based on a graph. I will discuss some of the ways interesting walks can be built from graphs. Of course, if a walk is based on a graph, then we might hope for interactions between properties of the graph and properties of the walk. I will discuss this too.