qat.opt.GraphColouring

class qat.opt.GraphColouring(graph, number_of_colours, **kwargs)

Specialization of the QUBO class for Graph Colouring.

This class allows for the encoding of a Graph Colouring problem for a given graph and a number of colours. The method produce_q_and_offset() is automatically called. It computes the \(Q\) matrix and QUBO energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent class QUBO and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance.

Reference

“Ising formulations of many NP problems”, A. Lucas, 2014 - Section 6.1.

import numpy as np
import networkx as nx
from qat.opt import GraphColouring

graph = nx.Graph()
graph.add_nodes_from(np.arange(4))
graph.add_edges_from([(0,1), (0,2), (1,2), (1,3), (2,3)])
number_of_colours = 3

graph_colouring_problem = GraphColouring(graph, number_of_colours)

print("To anneal the problem, the solver would need "
      + str(len(graph.nodes()) * number_of_colours) + " spins.")

To anneal the problem, the solver would need 12 spins.
Parameters

  • graph (networkx.Graph) – a networkx graph

  • number_of_colours (int) – the number of colours

get_best_parameters()

This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA), available in the QLM. However, the temperature parameters could also be used for simulated annealing (SA).

Returns

6-key dictionary containing

  • n_monte_carlo_updates (int) - the number of Monte Carlo updates

  • n_trotters (int) - the number of “classical replicas” or “Trotter replicas”

  • gamma_max (double) - the starting magnetic field

  • gamma_min (double) - the final magnetic field

  • temp_max (double) - the starting temperature

  • temp_min (double) - the final temperature

parse_result(result, inverse=False)

Returns the best approximated solution of the Graph Colouring problem from a list of samples

Parameters

result (BatchResult) – BatchResult containing a list of samples

Returns

The best partition among the samples thatrepresents the colour of each node

Return type

GraphPartitioningResult

qat.opt.graph_colouring.produce_q_and_offset(graph, number_of_colours)

Returns the \(Q\) matrix and the offset energy of the problem.

Parameters

  • graph (networkx.Graph) – a networkx graph

  • number_of_colours (int) – the number of colours