K-Clique Generator

Given an undirected graph with vertex set \(V\) and edge set \(E\), K-Clique consists in finding out whether there exists a complete subgraph of size \(K\). Annealing the problem requires \(\#V\) spins (one spin per vertex).

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

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]

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

combinatorial_result.display()
../../images/kclique_generator_result.png 
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="sqa") | 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]

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

combinatorial_result.display()
../../images/kclique_generator_result_annealing.png 
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="aqo")
aqo_batch = kclique_generator.generate(None, graph, 4, 5, 1)

Currently, the analog qpus that can be used to execute the underlying Schedule are only available on Qaptiva. Therefore, the generated aqo_batch here can be passed to Qaptiva for execution.