Algebraic Graph Theory and Quantum Physics

Abstract:
Somewhat surprisingly, work in quantum physics leads to interesting questions in algebraic graph theory. I will discuss three cases.
(1) Quantum walks: if 𝐴 is the adjacency matrix of a graph 𝑋, the unitary matrices 𝑈(𝑡)=exp(𝑖𝑡𝐴) determine a continuous quantum walk. Physicists ask whether, given vertices 𝑎 and 𝑏 in 𝑋, is there a time 𝑡 such that |𝑈(𝑡)𝑎,𝑏|=1? This is a purely graph theoretic question, but actual examples might be useful in the operation of a quantum computer.
(2) Geometry of lines: we want unit vectors 𝑧1,…,𝑧𝑚in 𝐶𝑑, such that |𝑧𝑖∗𝑧𝑗| takes the same value for all distinct indices 𝑖 and 𝑗. It is not hard to show that 𝑚≤𝑑2. The (open) question is whether this bound is always tight.
(3) Colouring problems: let 𝑆(𝑑) be the graph with the unit vectors in 𝑅𝑑 as its vertices, with two unit vectors adjacent if they are orthogonal. Any orthonormal basis for 𝑅𝑑 provides a clique of size 𝑑, so the chromatic number 𝜒(𝑆(𝑑)) of this graph is at least 𝑑. A corollary of work of Gleason on the foundations of quantum physics is that 𝜒(𝑆(𝑑))>𝑑 when 𝑑≥3. More recently physicists have introduced the notions of quantum colourings and quantum chromatic numbers. We have that 𝜒𝑞(𝑋)≤ 𝜒(𝑋) (for all 𝑋). One surprise is that the existing lower bounds on 𝜒(𝑋) are often valid lower bounds on 𝜒𝑞(𝑋).s


Biography:
 Chris Godsil is a Distinguished Professor Emeritus at the University of Waterloo. He is an internationally renowned leader in discrete mathematics whose work has had a profound and lasting influence on several areas of mathematics worldwide. In particular, he has been a pioneer in applying techniques from algebraic combinatorics to fundamental problems in quantum information theory. Professor Godsil has served the mathematical community in many important roles, including as a member of the Research Committee of the Canadian Mathematical Society, a member of the Speaker Selection Committee for the Combinatorics Section of the 1998 International Congress of Mathematicians, and as an organizer for major conferences such as the SIAM Conference on Discrete Mathematics (San Diego, 2002) and the Second CanaDAM Algebraic Approaches (with Karen Meagher). He has also supervised more than 30 graduate students. Conference (Montreal, 2009). He is a co-founder of the Journal of Algebraic Combinatorics and has served on the editorial boards of several leading journals, including the Australian Journal of Combinatorics, the Journal of Combinatorial Theory Series B, and Combinatorica. Professor Godsil’s research contributions include more than 120 papers in international journals, as well as several highly influential books, including Algebraic Combinatorics, Algebraic Graph Theory (with Gordon Royle), and The Erdős–Ko–Rado Theorem: Algebraic Approaches (with Karen Meagher). He has also supervised more than 30 graduate students.