Some students in my department this quarter hosted a reading group on quantum computing. Quantum computing is becoming more and more relevant and the topic attracted the participation of a diverse group of researchers. The best way to handle the scope of the topic and diversity of the participants was to invite volunteer speakers to give talks on the quantum analog of their own research area — “Quantum Circuit Lower Bounds,” “Quantum Game Theory,” and “QPSPACE” were among some of the topics. Naturally, I saw this as a great opportunity to understand more about quantum spectral graph theory. In this post I will outline some basic definitions and properties of quantum graphs, and as a follow up to my previous post on the connections between spectral geometry and graph theory, discuss isospectral properties of discrete and quantum graphs. Continue reading →

Spectral graph theory is the study of the intimate relationship of eigenvalues to different properties of graphs. Most typically the eigenvalues are associated to eigenfunctions of matrices associated to graphs known as Laplacians. Let $latex G = (V, E)$ be a weighted or unweighted undirected graph (there are simple extensions to directed graphs for many problems). Let $latex A$ be the adjacency matrix and let $latex D$ be the diagonal degree matrix, that is, $latex (D)_{ii} = d_i$, the degree of vertex $latex i$. Then a common definition for the Laplacian is $latex L = D-A$.

As I develop in my research in spectral graph theory, I am consistently amazed by the truth that many results in spectral graph theory can be seen as discrete analogues to results in spectral geometry. I am not accustomed to thinking of graphs as geometric objects, but in fact graph Laplacian matrices are nicely related to Laplace operators on Riemannian manifolds. In this post, I’d like to discuss a few of these relationships. Continue reading →