qat.opt.GraphPartitioning

class qat.opt.GraphPartitioning(graph, A, B=1, **kwargs)

Specialization of the Ising class for Graph Partitioning.

This class allows for the encoding of a Graph Partitioning problem for a given graph. The method produce_j_h_and_offset() is automatically called. It computes the coupling matrix \(J\), magnetic field \(h\) and Ising energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent class Ising and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance - see the Graph Partitioning notebook.

For right encoding we need \(\frac { A } { B } \geq \frac { min(2D, N) } { 8 }\) with \(D\) - the maximal degree of a node in the graph and \(N\) - the number of nodes.

Reference

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

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

graph = nx.Graph()
graph.add_nodes_from(np.arange(10))
graph.add_edges_from([(0,1), (0,4), (0,6), (1,2), (1,4), (1,7), (2,3), (2,5), (2,8),
                      (3,5), (3,9), (4,6), (4,7), (5,8), (5,9), (6,7), (7,8), (8,9)])

B = 2
A = 5

graph_partitioning_problem = GraphPartitioning(graph, A, B=B)

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

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

  • graph (networkx.Graph) – a networkx graph

  • A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.

  • B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1

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 Partitioning problem from a list of samples

Parameters

result (BatchResult) – BatchResult containing a list of samples

Returns

The best balanced partition among the samples with the minimum cut size

Return type

GraphPartitioningResult

qat.opt.graph_partitioning.produce_j_h_and_offset(graph, A, B=1)

Returns the \(J\) coupling matrix of the problem, along with the magnetic field \(h\) and the Ising energy offset. For right encoding we need \(\frac{A}{B} \geq \frac{min(2D, N)}{8}\) with \(D\) - the maximal degree of a node in the graph and \(N\) - the number of nodes.

Parameters

  • graph (networkx.Graph) – a networkx graph

  • A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.

  • B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1