Q Seminar: Eric Culf

Speaker: Eric Culf, University of Waterloo, Canada

Title: When are quantum graph homomorphisms undecidable?

Abstract: Constraint satisfaction problems (CSPs) are a natural class of decision problems where one must decide whether there is an assignment to variables that satisfies a given formula. Schaefer's dichotomy theorem, and its extension to all alphabets due to Bulatov and Zhuk, shows that CSP languages are either efficiently decidable, or NP-complete. It is possible to extend CSP languages to quantum assignments using the formalism of nonlocal games. Due to the equality of complexity classes MIP*=RE, general succinctly-presented entangled CSPs are RE-complete. We show that a wide range of NP-complete CSPs become RE-complete in this setting, by using a device called a commutativity gadget to make classical reductions quantum-sound. On the other hand, we show that for some CSPs, commutativity gadgets cannot exist owing to certain quantum symmetries. In this talk, I focus on graph CSPs, where the decision problem amounts to deciding if a quantum homomorphism exists between a pair of graphs; interesting examples arise in the context of complete graphs and cycle graphs. This talk is based on work with Kieran Mastel (arxiv.org/abs/2410.21223); and Josse van Dobben de Bruyn, Matthijs Vernooij, and Peter Zeman (arxiv.org/abs/2509.07835).