Entangled graph colouring with more than three colours is undecidable
The complexity of entangled graph colouring via polymorphisms
Computational Complexity
Summary
Deciding if you can colour a graph in certain special ways is a problem in computer science. The authors study a complicated version where variables relate to quantum-like 'entangled' assignments. They show that figuring out if a graph can be coloured with more than three colours in this entangled setting is impossible to decide by any computer program. To do this, they use advanced math concepts called polymorphisms to connect this problem to known hard problems.
What this means in practice
- •For quantum information engineers: Know that designing algorithms for entangled graph colouring with more than three colours cannot be guaranteed to terminate in general.
- •For complexity theorists: Use the result as a new hardness benchmark when studying quantum or entangled extensions of classical computational problems.
A theory result. No direct application yet.
Authors
Eric Culf
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.