Average mixing of continuous quantum walks

If X is a graph with adjacency matrix A, then we define H(t) to be the operator exp(it A). The Schur (or entrywise) product H (t) circle H(-t) is a doubly stochastic matrix and because of work related to quantum computing, we are concerned with the average mixing matrix (M) over cap (X), defined by (M) over cap (X) = lim(T ->infinity) 1/T integral(T)(0) H(t) circle H(-t) dt. In this paper we establish some of the basic properties of this matrix, showing that it is positive semidefinite and that its entries are always rational. We see that in a number of cases its form is surprisingly simple. Thus for the path on n vertices it is equal to 1/2n + 2 (2 J + 1 + T) where T is the permutation matrix that swaps j and n +1 - j for each j. If X is an odd cycle or, more generally, if X is one of the graphs in a pseudocyclic association scheme on n vertices with d classes, each of valency m, then its average mixing matrix is n - m + 1/n(2) J + m - 1/n I. (One reason this is interesting is that a graph in a pseudocyclic scheme may have trivial automorphism group, and then the mixing matrix is more symmetric than the graph itself.) (C) 2013 Elsevier Inc. All rights reserved.