Graph Partitioning Generator
Given an undirected graph with vertex set \(V\) and edge set \(E\), Graph Partitioning consists in partitioning the graph into two equally-sized subgraphs connected by the minimal number of edges. Annealing the problem needs \(\#V\) spins (one spin for each individual vertex).
The GraphPartitioningGenerator can be used to generate batches to solve the Graph Partitioning
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
from qat.generators import GraphPartitioningGenerator
from qat.plugins import ScipyMinimizePlugin
from qat.qpus import get_default_qpu
graph = nx.full_rary_tree(3, 6)
scipy_args = dict(method="COBYLA", tol=1e-5, options={"maxiter": 200})
graph_partitioning_application = GraphPartitioningGenerator(job_type="qaoa") | (ScipyMinimizePlugin(**scipy_args) | get_default_qpu())
combinatorial_result = graph_partitioning_application.execute(graph, 1)
print("The nodes in the first subgraph are", combinatorial_result.subsets[0])
print("The nodes in the second subgraph are", combinatorial_result.subsets[1])
The nodes in the first subgraph are [0, 2, 3]
The nodes in the second subgraph are [1, 4, 5]
The parsed combinatorial result can also be displayed with NetworkX using the
display() method:
combinatorial_result.display()
import networkx as nx
from qat.generators import GraphPartitioningGenerator
from qat.qpus import SimulatedAnnealing
from qat.core import Variable
from qat.opt.sqa_best_parameters import sqa_best_parameters_dicts
graph = nx.full_rary_tree(2, 30)
# Create a temperature function
t = Variable("t", float)
temp_max = sqa_best_parameters_dicts["GraphPartitioning"]["temp_max"]
temp_min = sqa_best_parameters_dicts["GraphPartitioning"]["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
graph_partitioning_application = GraphPartitioningGenerator(job_type="sqa") | SimulatedAnnealing(temp_t, n_steps)
combinatorial_result = graph_partitioning_application.execute(graph, 1)
print("The nodes in the first subgraph are", combinatorial_result.subsets[0])
print("The nodes in the second subgraph are", combinatorial_result.subsets[1])
The nodes in the first subgraph are [1, 3, 4, 7, 8, 9, 10, 15, 16, 17, 18, 19, 20, 21, 22]
The nodes in the second subgraph are [0, 2, 5, 6, 11, 12, 13, 14, 23, 24, 25, 26, 27, 28, 29]
Similarly, the function display() method can be used
to display the result:
combinatorial_result.display()
import networkx as nx
from qat.generators import GraphPartitioningGenerator
graph = nx.full_rary_tree(3, 6)
graph_partitioning_generator = GraphPartitioningGenerator(job_type="aqo")
aqo_batch = graph_partitioning_generator.generate(None, graph, 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.