News Archive
Can you hear the shape of a graph?
Deciding whether some graphs are actually the same or not is a computationally difficult problem, with important practical applications ranging from communication theory and computer architecture design to the study of social networks.
Can you hear the shape of a graph?
A graph is an abstract encapsulation of relationships, one which is commonly drawn as a series of points (vertices) connected by lines (edges). Three examples are shown in the figure on the left. While these three graphs look different, mathematically speaking graphs (A) and (C) are considered to be exactly the same graph. This is because there is a way of moving the vertices of graph (C) around until it lies perfectly on top of graph (A).
Deciding whether some graphs are actually the same or not is a computationally difficult problem, with important practical applications ranging from communication theory and computer architecture design to the study of social networks
For many years, graph theorists have analysed one particular mathematical technique for doing so – a technique which just happens to be equivalent to the physical problem of determining the quantum-mechanical spectrum of a single particle hopping around the sites of the graph! Physicists then suggested to graph theorists that the spectrum of two or more repulsively interacting particles on the graph could be even more useful for distinguishing graphs – a suggestion which has resulted in the identification of powerful new graph invariants.
For example, the three graphs in the figure have the same single particle energy spectrum (red lines) but because graph (B) has a different two-particle energy spectrum (blue lines) from (A) and (C) we are assured that it really is a different graph.
While numerical studies indicated that these new invariants were interesting (particularly since they can be efficiently calculated on a quantum computer), no analytic results were forthcoming until two quantum information theorists – Koenraad Audenaert and Terry Rudolph (Imperial College London) joined forces with two well known graph theorists – Chris Godsil (University of Waterloo) and Gordon Royle (University of Western Australia). They have made significant progress on results concerning the two-particle spectrum of a graph, in a paper which carries the hallmark of both combinatorial and matrix-analytical techniques favoured by each of the two communities.
References:
1) Constructing physically intuitive graph invariants, Terry Rudolph, quant-ph/0206068
2) Symmetric Squares of Graphs, Koenraad Audenaert, Chris Godsil, Gordon Royle and Terry Rudolph, math.CO/0507251
(Koenraad Audenaert and Terry Rudolph, October 2005)
Previous page: News
Next page: About QIP IRC