Abstract:
In this paper we demonstrate how to solve the chromatic sum problem using a D-Wave quantum computer. Starting from a BIP (binary integer programming) formulation, we develop a D-Wave feasible QUBO quadratic unconstrained binary optimisation) formulation of the chromatic sum problem. Our construction requires nk qubits for a graph of n vertices and upper bound of k colours. Further, we present the experimental results obtained by running several QUBOs on a D-Wave quantum computer.