Vertex Cover

Given an undirected graph with vertex set \(V\) and edge set \(E\), the problem 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 our VertexCover class (or VertexCoverGenerator) with \(\#V\) spins (one spin per vertex).

Solving this problem using the simulated annealing method requires the SimulatedAnnealing QPU.

import networkx as nx
import numpy as np
from qat.opt import VertexCover
from qat.qpus import SimulatedAnnealing
from qat.simulated_annealing import integer_to_spins
from qat.core import Variable

# Specify the graph
graph = nx.Graph()
graph.add_nodes_from(np.arange(6))
graph.add_edges_from([(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 5)])

# Impose constraints for the right encoding
B = 1
A = B + 0.01
vertex_cover_problem = VertexCover(graph, A=A, B=B)

# Extract parameters for SA
problem_parameters_dict = vertex_cover_problem.get_best_parameters()
n_steps = problem_parameters_dict["n_steps"]
temp_max = problem_parameters_dict["temp_max"]
temp_min = problem_parameters_dict["temp_min"]

# Create a temperature schedule and a QPU
tmax = 1.0
t = Variable("t", float)
temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)
sa_qpu = SimulatedAnnealing(temp_t=temp_t, n_steps=n_steps)

# Create a job and send it to the QPU
problem_job = vertex_cover_problem.to_job('sqa', tmax=tmax)
problem_result = sa_qpu.submit(problem_job)

# Extract and print the solution configuration
state = problem_result.raw_data[0].state.int  # raw_data is a list of Samples - one per computation
solution_configuration = integer_to_spins(state, len(graph.nodes()))
print("Solution configuration: \n" + str(solution_configuration) + "\n")
indices_spin_1 = np.where(solution_configuration == 1)[0]
number_of_colours = len(indices_spin_1)
print("One would need to colour " + str(number_of_colours) + " vertices, which are:\n" + str(indices_spin_1) + "\n")

Solution configuration: 
[ 1.  1. -1. -1. -1. -1.]

One would need to colour 2 vertices, which are:
[0 1]

<stdin>:31: UserWarning: If SQAQPU is used, gamma_t will be needed.

This example is also detailed in this notebook on solving Vertex Cover problems with SA.