Algebraic Graph Theory Seminar - Chris Godsil

Title: Quantum Colouring and Derangements

Abstract:

Work in quantum information has lead to the introduction of quantum colourings. In a sense, the idea is to colour the vertices of graphs using quantum measurements (a sequence of $d\times d$ projections summing to $I_d$) in place of elements of a finite set. The theory of quantum colourings shows both interesting analogies and interesting differences to the classical theory. My talk will give an introduction to this topic, based in part on the fact that we can reduce the amount of physics used by substituting ``unitary derangements'' (unitary matrices with zero diagonal) for measurements. (Since quantum physics is widely acknowledged to be crazy, using derangements seems natural.)