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 for the problem at hand. We propose unitary- as well as measurement-based quantum computations, also taking inspiration from answer set programming, a form of declarative programming close to traditional logic programming. The approach used is one in which we first generate arbitrary solutions to the problem, then 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 improvements.