QAOA MaxClique#

Problem description#

Given a Graph $G = (V, E)$ find a maximum clique, i.e., a subset of vertices $V^{'} \subset V$ such that all pairs of vertices are adjacent in the graph $G$ . Following the work of Hadfield et al., the MaxClique problem is solved by solving the MaxIndepSet problem on the complement graph.

Classical cost function#

create_max_clique_cl_cost_function(G)[source]#

Creates the classical cost function for an instance of the maximum clique problem for a given graph G.

Parameters:

Gnx.Graph: The Graph for the problem instance.

Returns:

cl_cost_functionfunction: The classical cost function for the problem instance, which takes a dictionary of measurement results as input.

MaxClique problem#

max_clique_problem(G)[source]#

Creates a QAOA problem instance with appropriate phase separator, mixer, and classical cost function.

Parameters:

Gnx.Graph: The graph for the problem instance.

Returns:

QAOAProblem: A QAOA problem instance for MaxClique for a given graph G.

Example implementation#

from qrisp import QuantumVariable
from qrisp.qaoa import QAOAProblem, RZ_mixer, create_max_indep_set_cl_cost_function, create_max_indep_set_mixer, max_indep_set_init_function
import networkx as nx

G = nx.erdos_renyi_graph(9, 0.7, seed =  133)
G_complement = nx.complement(G)
qarg = QuantumVariable(G.number_of_nodes())

qaoa_max_clique = QAOAProblem(cost_operator=RZ_mixer,
                                mixer=create_max_indep_set_mixer(G_complement),
                                cl_cost_function=create_max_indep_set_cl_cost_function(G_complement),
                                init_function=max_indep_set_init_function)
results = qaoa_max_clique.run(qarg=qarg, depth=5)

That’s it! In the following, we print the 5 most likely solutions together with their cost values.

cl_cost = create_max_indep_set_cl_cost_function(G_complement)

print("5 most likely solutions")
max_five = sorted(results.items(), key=lambda item: item[1], reverse=True)[:5]
for res, prob in max_five:
    print([index for index, value in enumerate(res) if value == '1'], prob, cl_cost({res : 1}))

Finally, we visualize the most likely solution.

most_likely = [index for index, value in enumerate(max_five[0][0]) if value == '1']
nx.draw(G, with_labels = True,
        node_color=['#FFCCCB' if node in most_likely else '#ADD8E6' for node in G.nodes()],
        edge_color=['#FFCCCB' if edge[0] in most_likely and edge[1] in most_likely else '#D3D3D3' for edge in G.edges()])