Quantum approaches to graph colouring

In this paper we investigate quantum algorithms for graph colouring problems, in particular for 2- and 3-colouring of graphs. Our main goal is to establish a set of quantum representations and operations suitable to the problem at hand. We propose unitary- as well as measurement-based quantum computations, taking inspiration also from answer set programming, a form of declarative programming close to traditional logic programming. The approach used is one in which we first generating arbitrary solutions to the problem, constraining these according to the problem's input. Though we do not achieve fundamental speed-ups, our algorithms show how quantum concepts can be used for programming and moreover exhibit structural differences. For example, we compute all possible colourings at the same time. We compare our algorithms with classical ones, highlighting how the same type of difficulties give rise to NP-complete behaviour, and propose possible solutions.