Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
This work addresses the complexity classification of quantum CSPs for theoretical computer scientists, providing a complete algebraic framework that resolves prior gaps in understanding.
The authors introduced quantum polymorphisms to characterize reductions between quantum constraint satisfaction problems (CSPs) and established a Galois connection framework, which they used to fully classify commutativity gadgets for relational structures—previously only partially known—and prove the undecidability of quantum CSPs parameterized by odd cycles and Siggers clauses.
We introduce the concept of quantum polymorphisms to the complexity theory of quantum constraint satisfaction. Via this notion, we build an algebraic framework of reductions between quantum CSPs, and we establish a Galois connection between quantum polymorphism minions and quantum relational constructions. By leveraging a contextuality property of quantum polymorphisms, we fully characterise the existence of commutativity gadgets for relational structures, introduced by Ji as a method for achieving quantum soundness of classical CSP reductions. Prior to our work, only a partial classification was known for a subclass of Boolean languages and for non-Boolean languages meeting specific structural conditions [Culf--Mastel, FOCS'25]. As an application of our framework, we prove that the quantum CSPs parameterised by odd cycles and the quantum CSP expressing quantum satisfiability of Siggers clauses are undecidable.