Algebraic Graph Theory - Chris Godsil

Title: Uniform Mixing and Quantum Walks

Abstract: ILet X be a graph with adjacency matrix A. A continuous quantum walk on X is a matrix-valued function of time U(t), defined by U(t) = exp(itA): The matrices U(t) are unitary and so, at a fixed time t, the squares of the absolute values of the entries of a row of U(t) form a probability density on the vertices of X; the properties of these densities aree of interest in quantum physics. The question we will consider is for which graphs is there a time t such that all entries of U(t) have the same absolute value. In this case we say that we have uniform mixing on X. This question is quite complicated. Thus uniform mixing occurs on the complete graphs K2, K3 and K4, but it does not take place on Kn when n > 4. We know that uniform mixing does not occur on even cycles, nor on cycles of prime length p for p > 3; we do not know what happens on C9, or on Cn when n is odd but not prime. If uniform mixing does occur at time t, then U(t) is a generalized Hadamard matrix, Since we know the generalized Hadamard matrices that can occur in the Bose-Mesner algebra of a strongly regular graph, we can determine the strongly regular graphs that admit uniform mixing. In my talk I will provide an introduction to what we know about this topic, and to the many open problems that remain.