Open Collections

Description

One of the typical ways to study quantum complexity is to take a set of classical constraints and see how they behave when quantum assignments are allowed. Examples include graph homomorphism games and k-colouring, amongst many others. A common pathway to analyse these complexity classes, both classically and quantum, is to prove reductions from one class to another. Many classical reductions exist, and they can often be lifted to quantum reductions whenever one has access to a so-called commutativity gadget. In this talk, I will introduce these notions and then show that the existence of non-classical quantum endomorphisms rules out the existence of commutativity gadgets. For example, there is no commutativity gadget for 4-colouring because S_4^+ is a non-classical quantum group. This connection can give a new motivation to study quantum automorphism groups and, more generally, quantum endomorphism monoids.