Max Cut Generator
The MaxCutGenerator
can be used to generate batches to solve the max cut 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
from qat.generators import MaxCutGenerator
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})
max_cut_application = MaxCutGenerator(job_type="qaoa") | (ScipyMinimizePlugin(**scipy_args) | get_default_qpu())
combinatorial_result = max_cut_application.execute(graph)
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 cost here is negative since all combinatorial optimization problems are defined as a minimization problem, so a factor of -1 is needed
print("The number of edges that are cut is", -1 * combinatorial_result.cost)
The nodes in the first subgraph are [0, 4, 5]
The nodes in the second subgraph are [1, 2, 3]
The number of edges that are cut is 5.0
<stdin>:10: 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()
Annealing job generation
import networkx as nx
from qat.generators import MaxCutGenerator
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["MaxCut"]["temp_max"]
temp_min = sqa_best_parameters_dicts["MaxCut"]["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
max_cut_application = MaxCutGenerator(job_type="annealing") | SimulatedAnnealing(temp_t, n_steps)
combinatorial_result = max_cut_application.execute(graph)
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 cost here is negative since all combinatorial optimization problems are defined as a minimization problem, so a factor of -1 is needed
print("The number of edges that are cut is", -1 * combinatorial_result.cost)
The nodes in the first subgraph are [1, 2, 4, 7, 8, 11, 12, 13, 14, 19, 20, 21, 22]
The nodes in the second subgraph are [0, 3, 5, 6, 9, 10, 15, 16, 17, 18, 23, 24, 25, 26, 27, 28, 29]
The number of edges that are cut is 28.0
<stdin>:17: 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()
Scheduling job generation
import networkx as nx
from qat.generators import MaxCutGenerator
graph = nx.full_rary_tree(3, 6)
max_cut_generator = MaxCutGenerator(job_type="schedule")
schedule_batch = max_cut_generator.generate(None, graph)
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.MaxCutGenerator(job_type='qaoa')
Specialization of the CombinatorialOptimizerGenerator class for generator that solves the Max Cut problem
- Parameters
job_type (str) – The job type of the batches to be generated. Can be either “qaoa”, “schedule” or “annealing”
- generate(specs, graph, **kwargs)
Generate a batch that solves the Max Cut 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
GraphPartitioningResult
that contains interpretable information- Parameters
specs (
HardwareSpecs
) – will be used to run the jobgraph (networkx.Graph) – a networkx graph to run the Max Cut algorithm on
- Returns
A parsed result of combinatorial optimization problem
- Return type