Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911559202111488 |
|---|---|
| author | Ciardo, Lorenzo Joubert, Gideo Mottet, Antoine |
| author_facet | Ciardo, Lorenzo Joubert, Gideo Mottet, Antoine |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_23445 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction Ciardo, Lorenzo Joubert, Gideo Mottet, Antoine Quantum Physics Computational Complexity Logic in Computer Science Combinatorics 81P45, 05C15 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. |
| title | Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction |
| topic | Quantum Physics Computational Complexity Logic in Computer Science Combinatorics 81P45, 05C15 |
| url | https://arxiv.org/abs/2511.23445 |