Graph Colouring with a Quantum Annealer

A guided research project in Quantum Computing.

← Quantum Computing projects

Experience Research Quantum Computing

Question

Can a quantum annealer find valid colourings of a graph?

A valid colouring appears as a low-energy state with no rule penalties.
A valid colouring appears as a low-energy state with no rule penalties.

Goals

  • Encode graph colouring as a binary energy function.
  • Test how graph size and penalty weights affect valid solutions.

Method

Give every vertex–colour choice a binary variable and penalize broken colouring rules.

  • Build QUBO terms for one colour per vertex and different colours across each edge.
  • Embed and sample the model on an annealer or simulator.
  • Decode the samples and compare validity and quality with a classical colouring method.