QUBO

Reduce graph-colouring models to efficient quadratic binary objectives for quantum annealing.

← Explore Research

Explore Research

Question

How can a graph-colouring model be reduced to QUBO form with far fewer auxiliary variables?

A graph-colouring problem becomes a higher-degree binary objective that must be reduced to the quadratic form accepted by a quantum annealer.
Motivation: compact graph-colouring encodings create terms above degree two, but a quantum annealer accepts pairwise terms. Each auxiliary bit introduced during reduction consumes another physical resource.
Ten cubic monomials reduced separately with ten auxiliary bits compared with one symmetric block reduced using two auxiliary bits.
Main idea: conventional methods reduce each monomial separately. The new method recognizes a homogeneous symmetric block and reduces its shared structure together.
Bar charts comparing monomial and symmetric reductions for an eight-vertex complete graph, showing fewer binary variables and quadratic terms.
Result for K₈ with eight colours: symmetric reduction uses 480 variables instead of 1,180 and 2,797 quadratic terms instead of 5,849.

Goals

  • Explain why compact graph-colouring models create terms above degree two.
  • Reduce repeated symmetric terms together instead of handling every monomial separately.
  • Measure the saving in binary variables and quadratic interactions before quantum annealing.

Method

The key is to find homogeneous symmetric parts of the objective and reduce their shared structure as one block.

  • Encode each vertex colour compactly with binary variables and penalize adjacent vertices that receive the same colour.
  • Identify large symmetric groups among the resulting higher-degree terms.
  • Reduce each symmetric group first, then apply ordinary monomial reduction only to the terms left over.
  • Compare auxiliary variables and quadratic terms on random graphs and complete graphs.

Read more