Various QAOA examples using Quixotic

Maximum Clique with QAOA

 
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)
Optimize for 10 iterations...
[========================================] 100%	  cost: -1.8832  iteration:10
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()
maximum_clique
minimum_vertex_cover
maximum_cut

Minimum Vertex Cover with QAOA

# # 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)
Optimize for 20 iterations...
[========================================] 100%	  cost: -1.1177  iteration:20
qo.plot_samples(probs)
qo.execute(50)
nodes, probs = qo.results(return_probs=True)
Optimize for 50 iterations...
[========================================] 100%	  cost: -1.2200  iteration:50
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")