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 Quantum Annealing (SQA) via the SQAQPU - see the Graph Partitioning notebook. This QPU also requires a few additional parameters, the specification of which may vary the quality of the solution. We therefore provide the best parameters found thus far through the method get_best_parameters().

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 annealing parameters found thus far after benchmarking. The parameters are needed to produce the entries of the SQAQPU used to solve a Graph Partitioning problem via Simulated Quantum Annealing (SQA).

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