KClique Generator

The KCliqueGenerator can be used to generate batches to solve the KClique problem on an input graph. Some examples using different types of job generation and QPUs on some simple graphs are shown below:

QAOA job generation

import networkx as nx
import numpy as np
from qat.generators import KCliqueGenerator
from qat.plugins import ScipyMinimizePlugin
from qat.qpus import get_default_qpu

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

scipy_args = dict(method="COBYLA", tol=1e-5, options={"maxiter": 200})
kclique_application = KCliqueGenerator(job_type="qaoa") | (ScipyMinimizePlugin(**scipy_args) | get_default_qpu())
combinatorial_result = kclique_application.execute(graph, 3, 5, 1)

print("The nodes of the complete subgraph are", combinatorial_result.clique)

The nodes of the complete subgraph are [1, 2, 3]
<stdin>:13: FutureWarning: adjacency_matrix will return a scipy.sparse array instead of a matrix in Networkx 3.0.

The parsed combinatorial result can also be displayed with networkx using the display() method:

combinatorial_result.display()
images/kclique_generator_result.png

Annealing job generation

import networkx as nx
import numpy as np
from qat.generators import KCliqueGenerator
from qat.qpus import SimulatedAnnealing
from qat.core import Variable
from qat.opt.sqa_best_parameters import sqa_best_parameters_dicts

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

# Create a temperature function
t = Variable("t", float)
temp_max = sqa_best_parameters_dicts["KClique"]["temp_max"]
temp_min = sqa_best_parameters_dicts["KClique"]["temp_min"]
temp_t = temp_min * t + temp_max * (1 - t)  # annealing requires going from a high to a very low temperature
n_steps = 5000

kclique_application = KCliqueGenerator(job_type="annealing") | SimulatedAnnealing(temp_t, n_steps)
combinatorial_result = kclique_application.execute(graph, 4, 5, 1)

print("The nodes of the complete subgraph are", combinatorial_result.clique)

The nodes of the complete subgraph are [0, 1, 2, 3]
<stdin>:23: FutureWarning: adjacency_matrix will return a scipy.sparse array instead of a matrix in Networkx 3.0.

Similarly, the function display() method can be used to display the result:

combinatorial_result.display()
images/kclique_generator_result_annealing.png

Scheduling job generation

import networkx as nx
import numpy as np
from qat.generators import KCliqueGenerator

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

kclique_generator = KCliqueGenerator(job_type="schedule")
schedule_batch = kclique_generator.generate(None, graph, 4, 5, 1)

Currently the analog qpus that can be used to execute the schedule are only available in the QLM. Therefore the generated schedule_batch here can be passed to a QLM for execution.

class qat.opt.generators.KCliqueGenerator(job_type='qaoa')

Specialization of the CombinatorialOptimizerGenerator class for generator that solves the KClique problem

Parameters

job_type (str) – The job type of the batches to be generated. Can be either “qaoa”, “schedule” or “annealing”

generate(specs, graph, K, A, B=1, **kwargs)

Generate a batch that solves the KClique problem on a particular graph. The batch can then be sent to a computational stack of plugins and QPU to be executed. The result will be parsed into KCliqueResult that contains interpretable information

Parameters

  • specs (HardwareSpecs) – will be used to run the job

  • graph (networkx.Graph) – a networkx graph to run the KClique algorithm on

  • 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 (double, optional) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1

Returns

A parsed result of combinatorial optimization problem

Return type

KCliqueResult