Quantum polymorphism characterisation of commutativity gadgets in all quantum models

Quantum Physics [Submitted on 1 Apr 2026] Quantum polymorphism characterisation of commutativity gadgets in all quantum models Eric Culf, Josse van Dobben de Bruyn, Peter Zeman Commutativity gadgets provide a technique for lifting classical reductions between constraint satisfaction problems to quantum-sound reductions between the corresponding nonlocal games. We develop a general framework for commutativity gadgets in the setting of quantum homomorphisms between finite relational structures. Building on the notion of quantum homomorphism spaces, we introduce a uniform notion of commutativity gadget capturing the finite-dimensional quantum, quantum approximate, and commuting-operator models. In the robust setting, we use the weighted-algebra formalism for approximate quantum homomorphisms to capture corresponding notions of robust commutativity gadgets. Our main results characterize both non-robust and robust commutativity gadgets purely in terms of quantum polymorphism spaces: in any model, existence of a commutativity gadget is equivalent to the collapse of the corresponding quantum polymorphisms to classical ones at arity |A|^2, and robust gadgets are characterized by stable commutativity of the appropriate weighted polymorphism algebra. We use this characterisation to show relations between the classes of commutativity gadget, notably that existence of a robust commutativity gadget is equivalent to the existence of a corresponding non-robust one. Finally, we prove that quantum polymorphisms of complete graphs K_n have a very special structure, wherein the noncommutative behaviour only comes from the quantum permutation group S_n^+. Combining this with techniques from combinatorial group theory, we construct separations between commutativity-gadget classes: we exhibit a relational structure admitting a finite-dimensional commutativity gadget but no quantum approximate gadget, and, conditional on the existence of a non-hyperlinear group, a structure admitting a quantum approximate commutativity gadget but no commuting-operator gadget. Comments: 44 pages, 3 figures Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Operator Algebras (math.OA) Cite as: arXiv:2604.01408 [quant-ph]   (or arXiv:2604.01408v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.01408 Focus to learn more Submission history From: Eric Culf [view email] [v1] Wed, 1 Apr 2026 21:15:32 UTC (45 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.CC math math.OA References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)