We introduce the concept of quantum polymorphisms to the complexity theory of non-local games. We use this notion to give a full characterisation of 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, a classification was only known in the Boolean case [Culf--Mastel, STOC'25]. As an application of our framework, we prove that the entangled CSP parameterised by odd cycles is undecidable. Furthermore, we establish a quantum version of Galois connection for entangled CSPs in the case of non-oracular quantum homomorphisms.

翻译：我们将量子多态性概念引入非局域博弈的复杂性理论中。利用这一概念，我们完整刻画了关系结构交换性构造器的存在性——该构造器由Ji提出，作为实现经典CSP归约量子可靠性的方法。在我们的工作之前，仅布尔情形存在已知分类[Culf--Mastel, STOC'25]。作为框架的应用，我们证明了以奇环为参数的纠缠CSP是不可判定的。此外，我们在非预言机量子同态情形下，为纠缠CSP建立了伽罗瓦连接的量子版本。