qat.opt.KClique

class qat.opt.KClique(graph, K, A, B=1, **kwargs)

Specialization of the QUBO class for K-Clique.

This class allows for the encoding of a K-Clique problem for a given graph and positive factors \(K, A, B\). 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 Quantum Annealing (SQA) via the SQAQPU - see the KClique 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 a right encoding, one should ensure that \(A > B * K\).

Reference: “Ising formulations of many NP problems”, A. Lucas, 2014 - Section 2.3.

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

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

B = 1
K = 3
A = B*K + 1

k_clique_problem = KClique(graph, K, 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 6 spins.

Parameters

graph (networkx.Graph) – a networkx graph
K (int) – the size of the clique
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 K-Clique 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 K-Clique problem from a list of samples

Parameters: result (BatchResult) – BatchResult containing a list of samples
Returns: The best partition among the samples with a K-clique as the first subset
Return type: GraphPartitioningResult

qat.opt.k_clique.produce_q_and_offset(graph, K, A, B=1)

Returns the \(Q\) matrix and the offset energy of the problem. The constant \(A\) should be bigger than \(K*B\) for a right encoding. They are also all positive.

Parameters

graph (networkx.Graph) – a networkx graph
K (int) – the size of the clique
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