The complexity of entangled graph colouring via polymorphisms
Abstract
Constraint satisfaction problems (CSPs) with operator assignments to the variables provide a well-structured setting to study the decision complexity of the entangled value of classes of nonlocal games. Due to the CSP dichotomy theorem, the complexity of constraint satisfaction problems with classical assignments can be fully understood by studying the symmetries of the CSP, in terms of the polymorphisms of the underlying relational structure. In this work, we show that the polymorphism-based reductions between CSPs can be generalised to gap-preserving reductions between entangled CSPs based on an entangled analogue of the polymorphisms. This reduction allows us to show undecidability of entangled graph colouring with more than three colours, a problem that has proved resistant to prior hardness reductions based on commutativity gadgets.
Related
- Managing complexity for integrated fusion reactor design using a differentiable graph-based MDAO framework: PROCESS as a case study
- Quantum Query Complexity of Persistence Statistics in Graph Zigzags
- Entangled Merged Pairs: The Observation-Boundary Principle
- Simulation of quantum entangled states by classical probabilistic models
- Quantum matter is weakly entangled at low energies
BibTeX
@misc{culf2026complexity,
title = {{The complexity of entangled graph colouring via polymorphisms}},
author = {Eric Culf},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02565},
eprint = {2610.02565},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02565},
}
RIS
TY - UNPB
TI - The complexity of entangled graph colouring via polymorphisms
AU - Eric Culf
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02565
UR - https://arxiv.org/abs/2610.02565
AB - Constraint satisfaction problems (CSPs) with operator assignments to the variables provide a well-structured setting to study the decision complexity of the entangled value of classes of nonlocal games. Due to the CSP dichotomy theorem, the complexity of constraint satisfaction problems with classical assignments can be fully understood by studying the symmetries of the CSP, in terms of the polymorphisms of the underlying relational structure. In this work, we show that the polymorphism-based reductions between CSPs can be generalised to gap-preserving reductions between entangled CSPs based on an entangled analogue of the polymorphisms. This reduction allows us to show undecidability of entangled graph colouring with more than three colours, a problem that has proved resistant to prior hardness reductions based on commutativity gadgets.
ER -