Vertex Cover Generator
Given an undirected graph with vertex set \(V\) and edge set \(E\), Vertex Cover consists in finding the smallest number of nodes to be coloured, such that every edge has a coloured vertex. As an addition, we want to know which these vertices are. To anneal this problem we would need \(\#V\) spins (one spin per vertex).
The VertexCoverGenerator can be used to generate batches to solve the Vertex Cover 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 VertexCoverGenerator
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})
vertex_cover_application = VertexCoverGenerator(job_type="qaoa") | (ScipyMinimizePlugin(**scipy_args) | get_default_qpu())
combinatorial_result = vertex_cover_application.execute(graph, 10, 5)
print("The nodes in the subgraph that forms a cover are", combinatorial_result.cover)
print("The number of nodes in the cover is", len(combinatorial_result.cover))
The nodes in the subgraph that forms a cover are [0, 1]
The number of nodes in the cover is 2
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 VertexCoverGenerator
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(3, 6)
# Create a temperature function
t = Variable("t", float)
temp_max = sqa_best_parameters_dicts["VertexCover"]["temp_max"]
temp_min = sqa_best_parameters_dicts["VertexCover"]["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
vertex_cover_application = VertexCoverGenerator(job_type="annealing") | SimulatedAnnealing(temp_t, n_steps)
combinatorial_result = vertex_cover_application.execute(graph, 10, 5)
print("The nodes in the subgraph that forms a cover are", combinatorial_result.cover)
print("The number of nodes in the cover is", len(combinatorial_result.cover))
The nodes in the subgraph that forms a cover are [0, 1]
The number of nodes in the cover is 2
Similarly, the method display() can be used
to display the result:
combinatorial_result.display()
import networkx as nx
from qat.generators import VertexCoverGenerator
graph = nx.full_rary_tree(3, 6)
vertex_cover_generator = VertexCoverGenerator(job_type="schedule")
schedule_batch = vertex_cover_generator.generate(None, graph, 10, 5)
Currently the analog qpus that can be used to execute the schedule are only available on Qaptiva. Therefore the generated schedule_batch here can be passed to Qaptiva for execution.