Information-processing tasks modelled by homomorphisms between relational structures can witness quantum advantage when entanglement is used as an extra computational resource. In this talk, I will show that the occurrence of quantum advantage is determined by the same type of algebraic structure (known as a minion) that captures the polymorphism identities of CSPs and, thus, CSP complexity. By studying the structure of the quantum minion and making use of classical results from the algebraic approach to CSPs, I will then show a characterisation of the graphs that have quantum advantage. Finally, I will introduce a natural version of quantum advantage that is linked to promise CSPs.
I will discuss the history and status of surjective constraint satisfaction problems, by covering what I know to be the principal results on this problem family, and culminating in a discussion of a unifying framework for a number of hardness results [arXiv:2005.11307].
I will give a short introduction to Promise CSPs, for the benefit of those not already involved in PCSP research.
In the PCSP, one is given a system of constraints, each with a “strong version” and a “weak version”, and is tasked with outputting Yes if there exists a solution to the strong version of the constraints, or No if there does not even exist a solution to the weak version of the constraints. One fascinating example of such problem is PCSP(1-in-3, NAE): given a 3-uniform hypergraph, output Yes if there exists a 1-in-3 colouring, and No if there does not even exist a non-monochromatic 2-colouring. While both the 1-in-3 and the NAE problems are NP-hard, their promise combination PCSP(1-in-3, NAE) is known to be tractable. Where is the boundary between hardness and tractability? In this talk, I will present a complexity dichotomy for the class of PCSPs obtained by weakening the “1-in-3 vs. NAE” promise from the left and from the right.
Joint work with Lorenzo Ciardo, Andrei Krokhin, Marcin Kozik, Standa Živný [arXiv:2302.03456].
In this talk, I provide an overview of the current state of the infinite-domain CSP. We discuss recent progress, challenges, and connections to other related fields such as finite-domain PCSP.