05C50 Online Seminar: Lorenzo Ciardo

A broad class of computational tasks can be phrased as the problem of determining whether two cooperating players, Alice and Bob, can convince a referee that a given statement involving relations between variables is true. Classic examples include colouring the vertices of a graph so that adjacent vertices receive different colours, identifying large independent sets or cliques in a graph, solving systems of linear equations, and finding satisfying assignments to CNF formulas. From this perspective, understanding the complexity of such tasks amounts to analysing how difficult it is for Alice and Bob to devise a winning strategy for the corresponding game.

This viewpoint naturally gives rise to a quantum variant of the problem, in which Alice and Bob are allowed to use shared entanglement to enhance their strategies. In this talk, after a brief introduction to the theory of such games (with no prior knowledge of quantum computing assumed), I will present recent joint work with Gideo Joubert and Antoine Mottet on the complexity of quantum games.

A key insight of this work is that the quantum analogue of an object known as a polymorphism (which has been studied in graph theory and classical complexity theory for decades) precisely characterises when traditional methods for analysing classical games extend to the quantum setting. The main challenge, therefore, is to understand the structure of quantum polymorphisms. Since these objects can ultimately be described as collections of orthogonal projectors satisfying certain geometric conditions, this leads to a purely matrix-theoretic problem, that will be explored in the end of the talk.