qat.opt.MaxCut

class qat.opt.MaxCut(graph, **kwargs)

Specialization of the Ising class for Max Cut.

This class allows for the encoding of a Max Cut problem for a given graph. The method produce_j_h_and_offset() is automatically called. It calculates 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 Max Cut 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().

Reference

Maximum cut, Theoretical physics, Wikipedia.

import networkx as nx
from qat.opt import MaxCut

graph = nx.full_rary_tree(2, 2**8)

maxcut = MaxCut(graph)

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

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

graph (networkx.Graph) – a networkx graph

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

Parameters

result (BatchResult) – BatchResult containing a list of samples

Returns

The best partition among the samples with the maximum cut size

Return type

GraphPartitioningResult

qat.opt.max_cut.produce_j_h_and_offset(graph)

Returns the \(J\) coupling matrix of the problem, along with the magnetic field \(h\) and the Ising energy offset.

Parameters

graph (networkx.Graph) – a networkx graph