Introduction
Let $A$ be the adjacency matrix of a graph, with the spectral decomposition \[A = \sum_r \theta_r E_r.\] The continuous quantum walk is \[U(t) = \exp(itA) = \sum_r e^{i\theta_r t} E_r.\] The probability distributions of the walk are given by the mixing matrix \[M(t) = U(t) \circ U(-t).\] In general this does not converge. However, the average over time \[\frac{1}{T} \int_0^T M(t) dt\] does converge to the average mixing matrix \[\widehat{M} = \sum_r E_r \circ E_r.\] The average mixing matrix is symmetric and doubly stochastic, so each column is a probability distribution. We compute the entropy of each column and sum them up. This sum measures how far $\widehat{M}$ is from being flat.
The following is our data in .sobj format on trees and connected graphs.
- The entropy sum for trees on up to 14 vertices. data
- The entropy sum for connected graph on up to 8 vertices. data
There are graphs with the same entropy sum. Here are some examples.