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.

Let’s begin by setting the scene. Let X be a vector space equipped with an inner product (also known as a Hilbert space) and let T: X → X be a self-adjoint bounded linear operator on the vector space with domain D(T). (If these terms are foreign to you, don’t worry too much. It is enough to accept that the Laplacians we’ll be talking about come with things called eigenvalues — keep reading!) The point spectrum of T is

σ_p(T) = { λ | ∃ some u in D(T) with Tu = λu }

We call these λ the eigenvalues of T, and they will be our main players.

Graphs and Laplace operators

Let’s begin with something comfy — discrete graphs. That is, a collection of vertices, V, and edges, E, connecting the vertices. In the discrete graph world, when we talk about functions on the graph we mean a function over the vertices. Most often, this function will assign a real number to each vertex in the graph, something like this: φ: V → R.  The discrete Laplace operator (or simply the Laplacian when talking about graphs specifically) can be described by its action on an arbitrary such φ:

(Lφ)(v) = ∑_u~v (φ(u) – φ(v)) = (D – A)φ(v)

(Take a look at my previous post if this looks like nonsense.)

An important question in spectral geometry is

To what degree does the spectrum of the Laplace operator determine the underlying space?

That is, what can the eigenvalues of the graph Laplacian tell us about the graph itself? In this post, I’ll explore this question and specifically how quantum graph spectra behave in somewhat unexpected ways.

Graph connectivity

Again, before tackling quantum graphs, lets become a little more familiar with the discrete setting. If the graph has n vertices, the size of the discrete Laplacian will be n x n. The discrete Laplacian is positive semidefinite, and so is has exactly n non-negative real eigenvalues 0 = λ₀ ≤ λ₁ ≤ … ≤  λ_n-1. The second smallest eigenvalue, λ₁ is known as the algebraic connectivity of the graph, because it provides certain bounds on how “connected” the graph is. That is, the larger λ₁ is, the more connected the graph. Namely, by adding an edge between two vertices in the graph, λ₁ becomes greater or stays the same, but never decreases.

This seems simple enough, but already things get wacky with quantum graphs.

A quantum graph is a simple graph (a set of vertices and set of undirected edges with no self-loops or multiedges) now with lengths associated to each edge. A first difference between a quantum graph and a typical graph is that things are no longer discrete. Now when we think of function on the graph, we think of a function that operates on the vertices and all points along the edges. The last piece that defines a quantum graph is a self-adjoint differential operator, which acts much like the Laplacian on discrete graphs. Now when we speak about the spectrum, we are referring to eigenvalues of this operator.

So what can be said about the connectivity about a quantum graph? Well, let’s think about adding an edge between two existing vertices. In the discrete case, adding an edge essentially made the two endpoints “closer” in graph terms. In the quantum case, however, we are now adding to the total length of the graph, since each edge has an associated length and adds all points along the edge. So, when the edge is long enough, we are actually decreasing the connectivity of the graph! That is, by adding this edge we may be shrinking λ₁. The exact statement is given by Kurasov et al. in this paper, and includes the specific conditions on the edge for which the connectivity shrinks.

So is there a way to change the connectivity without adding length to the graph? The same paper tells us there is! Namely, if we change the graph by picking two vertices and joining them together, but keeping the set of edges the same, we can increase connectivity! Their proof is some clever manipulation of the Rayleigh quotient to show that λ₁ for the newly obtained graph is at least as big as λ₁ in the original.

One fun consequence of this is the fact that the most highly connected quantum graph is the flower graph with n loops attached to one vertex. Tell that to your sweetheart next time you bring them daisies.

                       The flower graph with n loops has the largest spectral gap among all graphs formed by a given set of edges.

Hearing the shape of a quantum graph

To end, we’ll have just a bit of fun. Last time we asked whether or not, given a set of eigenvalues, it is possible to determine the shape of the graph. This is related to the question of hearing the shape of a drum given its fundamental tone.

We said generally that it is possible to have non-isomorphic graphs share the same spectrum (isospectral). So, unfortunately, it is not possible to hear the shape of a graph (or a drum, for that matter). But how bad are our chances for discrete vs. quantum graphs? Well, for discrete graphs, our chances are pretty bad. It has been shown that there are families of non-isomorphic isospectral graphs of size that grow exponentially in the number of edges. That’s a lot of graphs that sound the same! The quantum case? Well, according to Ralf Rueckriemen, who did his thesis on quantum graph spectra, we at least know that any family of isospectral quantum graphs is finite. So if you really want a better shot at hearing the shape of a graph, go quantum!