Group for Research in Decision Analysis

Quantum chromatic numbers and the conjectures of Connes and Tsirelson

Vern Paulsen University of Waterloo, Canada

It is possible to characterize the chromatic number of a graph in terms of a game. It is the fewest number of colours for which a winning strategy exists using classical random variables to a certain graph colouring game. If one allows the players to use quantum experiments to generate their random outcomes, then for many graphs this game can be won with far fewer colours. This leads to the definition of the quantum chromatic number of a graph. However, there are several mathematical models for the set of probability densities generated by quantum experiments and whether or not these models agree depends on deep conjectures of Connes and Tsirelson. Thus, there are potentially several "different" quantum chromatic numbers and computing them for various graphs gives us a combinatorial means to test these conjectures. In this talk I will present these ideas and some of the results in this area. I will only assume that the audience is familiar with the basics of Hilbert space theory and assume no background in quantum theory.

Free entrance.
Welcome to everyone!