Algebraic Graph Theory and Quantum Physics

COLLOQUIUM ANNOUNCEMENT: SPMS DISTINGUISHED SPEAKER SERIES

Abstract

Somewhat surprisingly, work in quantum physics leads to interesting questions in algebraic graph theory. This connection goes a long way back, but has become much stronger because of recent developments in quantum information theory. I will discuss three particular cases. Quantum walks: these are analogs of classical random walks. If A is the adjacency matrix of a graph then the unitary matrices 𝑈(𝑡), defined by 𝑈 𝑡 = exp 𝑖𝑡𝐴 , give us a continuous quantum walk. Physicists ask whether, given vertices 𝑎 and 𝑏, is there a time 𝑡 such that |𝑈(𝑡)𝑎,𝑏| = 1. This is a purely graph theoretic question (although actual examples might turn out to be useful in the operation of a quantum computer). Colouring problems: let 𝑆(𝑑) be the graph with the unit vectors in ℝ𝑑 as its vertices, where two unit vectors are adjacent if they are orthogonal. Any orthonormal basis for ℝ𝑑 corresponds to a clique of size 𝑑, so the chromatic number 𝜒(𝑆(𝑑)) of this graph is at least 𝑑. A corollary of the work of Gleason on the foundations of quantum physics is that 𝜒(𝑆(𝑑)) > 𝑑 when 𝑑 ≥ 3. More recently, physicists have introduced the notion of a quantum colouring, hence each graph 𝑋 has a quantum chromatic number 𝜒𝑞(𝑋). We have that 𝜒𝑞(𝑋) ≤ 𝜒(𝑋). One surprise is that the existing lower bounds on 𝜒(𝑋) are often valid lower bounds on 𝜒𝑞(𝑋) . Geometry of lines: in attempting to efficiently extract information from a quantum system, physicists are led to geometric problems. To describe one that is easy to state, suppose we want unit vectors 𝑧1, 𝑧2,…, 𝑧𝑚 in ℂ 𝑑 , such that |𝑧𝑖 ∗ 𝑧𝑗| takes the same value for all distinct indices 𝑖 and 𝑗 (a so-called set of equiangular lines). It is not hard to show that 𝑚 ≤ 𝑑 2 . The (open) question is whether this bound can be realized in all cases. The real version of this problem has a strong combinatorial flavour, and has been studied by many people.

Speaker Biography

Chris Godsil is a professor at the department of Combinatorics and Optimization in the Mathematics Faculty at the University of Waterloo. Chris is a research leader in discrete mathematics and has been (and continues to be) hugely influential in many different fields of mathematics around the world. Recently, Chris has been a pioneer in using techniques from algebraic combinatorics to tackle some fundamental questions in quantum information theory. He has served as a member of the Research Committee of the Canadian Mathematics Society, on the Speaker Selection Committee for the Combinatorics Session of the 1998 International Mathematics Congress, on the organizing committee for the SIAM Conference on Discrete Mathematics (San Diego, August 2002), and for the second Canadam Conference (Montreal, May 2009). He is a cofounder of the Journal of Algebraic Combinatorics and serves on the editorial board of the Australasian Journal of Combinatorics, the Journal of Combinatorial Theory Series B, and Combinatorica. His extensive contributions to mathematical research include three very successful books, Algebraic Combinatorics, Algebraic Graph Theory (co-authored with Gordon Royle), The Erdős-Ko-Rado Theorem: Algebraic Approaches (co-authored with Karen Meagher), and over 120 papers in research journals. He has supervised over 30 graduate students, many of whom have become successful academics.

Host: Dr Gary Greaves