Existence and nonexistence of commutativity gadgets for entangled CSPs

Abstract:Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the corresponding entangled CSPs. This has been done, for instance, for NP-complete boolean CSPs and 3-colouring in the work of Culf and Mastel. For many CSPs over larger alphabets, including $k$-colouring when $k \geq 4$, it is not known whether or not commutativity gadgets exist, or if the entangled CSP is decidable. In this paper, we initiate a systematic study of commutativity gadgets and prove the first known obstruction to their existence. We do this by extending the definition of the quantum automorphism group of a graph to the quantum endomorphism monoid of a CSP, and showing that a CSP with non-classical quantum endomorphism monoid does not admit a commutativity gadget. As a consequence of this, we get that no commutativity gadget exists for $k$-colouring when $k \geq 4$. However, we construct a commutativity gadget for an alternate way of presenting $k$-colouring as a nonlocal game, the oracular setting. Furthermore, we prove an easy to check sufficient condition for the quantum endomorphism monoid to be non-classical, extending a result of Schmidt for the quantum automorphism group of a graph, and use this to give examples of CSPs that do not admit a commutativity gadget. We also show that existence of commutativity gadgets and oracular commutativity gadgets is equivalent for graphs with no four-cycle; and that the odd cycles and the odd graphs have a commutative quantum endomorphism monoid, leaving open the possibility that they might admit a commutativity gadget.

56 pages, 2 figures. v2: removed Sec. 5.3, which was based on an erroneous result; added more exposition to the introduction; small technical fixes

Quantum Physics (quant-ph); Computational Complexity (cs.CC); Operator Algebras (math.OA)

arXiv:2509.07835 [quant-ph]

(or arXiv:2509.07835v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2509.07835 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.