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:

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]

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

combinatorial_result.display()

SQA job generation

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

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_application = KCliqueGenerator(job_type="sqa") | SQAQPU()
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()

AQO job generation

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

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_application = KCliqueGenerator(job_type="aqo") | AnalogQPU()
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]

The same example as with the Annealing job generation is used here. Therefore, the corresponding figure will be the same when displayed with the display() method.