Various QAOA examples using Quixotic
import networkx as nx
n_nodes = 6
p = 0.5 # probability of an edge
seed = 1967
g = nx.erdos_renyi_graph(n_nodes, p=p, seed=seed)
positions = nx.spring_layout(g, seed=seed)
nx.draw(g, with_labels=True, pos=positions, node_size=600)
from quixotic.core import QAOA
qo = QAOA(g, task='maximum_clique')
qo.execute()
nodes, probs = qo.results(return_probs=True)
sub = g.subgraph(nodes)
nx.draw(g, pos=positions, with_labels=True)
nx.draw(sub, pos=positions, node_color="r", edge_color="r")
qo.plot_samples(probs)
QAOA.supported_tasks()
# # input graph
# import networkx as nx
# edges = [(0, 1), (1, 2), (2, 0), (2, 3)]
# g = nx.Graph(edges)
# seed = 1967
# positions = nx.spring_layout(g, seed=seed)
# nx.draw(g, with_labels=True, pos=positions, node_size=600)
import networkx as nx
n_nodes = 6
p = 0.5 # probability of an edge
seed = 1967
g = nx.erdos_renyi_graph(n_nodes, p=p, seed=seed)
positions = nx.spring_layout(g, seed=seed)
nx.draw(g, with_labels=True, pos=positions, node_size=600)
from quixotic.core import QAOA
qo = QAOA(g, task='minimum_vertex_cover', n_layers=2)
qo.execute(20)
nodes, probs = qo.results(return_probs=True)
qo.plot_samples(probs)
qo.execute(50)
nodes, probs = qo.results(return_probs=True)
qo.plot_samples(probs)
sub = g.subgraph(nodes)
nx.draw(g, pos=positions, with_labels=True)
nx.draw(sub, pos=positions, node_color="r", edge_color="r")
Interestingly, after the additional iterations, our approximation is slightly closer to the ground truth than the Local Ratio algorithm in networkx that simply returns all nodes. The Local Ratio algorithm returns "a set of vertices whose weight sum is no more than 2 * OPT" (see this post for more information).
from networkx.algorithms.approximation.vertex_cover import *
nx_nodes = min_weighted_vertex_cover(g)
# plot nodes comprising the solution
sub = g.subgraph(nx_nodes)
nx.draw(g, pos=positions, with_labels=True)
nx.draw(sub, pos=positions, node_color="r", edge_color="r")