Max Clique Problem¶

Background¶

The problem is in graph theory. A clique is a subset of vertices in a graph such each pair of them is adjacent to each other.

The max clique problem is given a graph $G = (V,E)$, find the maximal clique in the graph. It is known to be in the NP-hard complexity class.

Solving the problem with classiq¶

Necessary Packages¶

In this demo, besides the classiq package, we'll use the following packages:

In [ ]:

%%capture
! pip install 'networkx[default]'
! pip install pyomo

%%capture ! pip install 'networkx[default]' ! pip install pyomo

Define the optimization problem¶

We encode each node

In [ ]:

import networkx as nx
import numpy as np
import pyomo.environ as pyo


def define_max_clique_model(graph):
    model = pyo.ConcreteModel()

    # each x_i states if node i belongs to the cliques
    model.x = pyo.Var(graph.nodes, domain=pyo.Binary)
    x_variables = np.array(list(model.x.values()))

    # define the complement adjacency matrix as the matrix where 1 exists for each non-existing edge
    adjacency_matrix = nx.convert_matrix.to_numpy_array(graph, nonedge=0)
    complement_adjacency_matrix = (
        1
        - nx.convert_matrix.to_numpy_array(graph, nonedge=0)
        - np.identity(len(model.x))
    )

    # constraint that 2 nodes without edge in the graph cannot be chosen together
    model.clique_constraint = pyo.Constraint(
        expr=x_variables @ complement_adjacency_matrix @ x_variables == 0
    )

    # maximize the number of nodes in the chosen clique
    model.value = pyo.Objective(expr=sum(x_variables), sense=pyo.maximize)

    return model

import networkx as nx import numpy as np import pyomo.environ as pyo def define_max_clique_model(graph): model = pyo.ConcreteModel() # each x_i states if node i belongs to the cliques model.x = pyo.Var(graph.nodes, domain=pyo.Binary) x_variables = np.array(list(model.x.values())) # define the complement adjacency matrix as the matrix where 1 exists for each non-existing edge adjacency_matrix = nx.convert_matrix.to_numpy_array(graph, nonedge=0) complement_adjacency_matrix = ( 1 - nx.convert_matrix.to_numpy_array(graph, nonedge=0) - np.identity(len(model.x)) ) # constraint that 2 nodes without edge in the graph cannot be chosen together model.clique_constraint = pyo.Constraint( expr=x_variables @ complement_adjacency_matrix @ x_variables == 0 ) # maximize the number of nodes in the chosen clique model.value = pyo.Objective(expr=sum(x_variables), sense=pyo.maximize) return model

Initialize the model with parameters¶

In [ ]:

graph = nx.erdos_renyi_graph(7, 0.6, seed=79)
nx.draw_kamada_kawai(graph, with_labels=True)
max_clique_model = define_max_clique_model(graph)

graph = nx.erdos_renyi_graph(7, 0.6, seed=79) nx.draw_kamada_kawai(graph, with_labels=True) max_clique_model = define_max_clique_model(graph)

Setting Up the Classiq Problem Instance¶

In order to solve the Pyomo model defined above, we use the Classiq combinatorial optimization engine. For the quantum part of the QAOA algorithm (QAOAConfig) - define the number of repetitions (num_layers):

In [ ]:

from classiq import construct_combinatorial_optimization_model
from classiq.applications.combinatorial_optimization import OptimizerConfig, QAOAConfig

qaoa_config = QAOAConfig(num_layers=20)

from classiq import construct_combinatorial_optimization_model from classiq.applications.combinatorial_optimization import OptimizerConfig, QAOAConfig qaoa_config = QAOAConfig(num_layers=20)

For the classical optimization part of the QAOA algorithm we define the maximum number of classical iterations (max_iteration) and the $\alpha$-parameter (alpha_cvar) for running CVaR-QAOA, an improved variation of the QAOA algorithm [3]:

In [ ]:

optimizer_config = OptimizerConfig(max_iteration=1, alpha_cvar=1)

optimizer_config = OptimizerConfig(max_iteration=1, alpha_cvar=1)

Lastly, we load the model, based on the problem and algorithm parameters, which we can use to solve the problem:

In [ ]:

qmod = construct_combinatorial_optimization_model(
    pyo_model=max_clique_model,
    qaoa_config=qaoa_config,
    optimizer_config=optimizer_config,
)

qmod = construct_combinatorial_optimization_model( pyo_model=max_clique_model, qaoa_config=qaoa_config, optimizer_config=optimizer_config, )

We also set the quantum backend we want to execute on:

In [ ]:

from classiq import set_execution_preferences
from classiq.execution import ClassiqBackendPreferences, ExecutionPreferences

backend_preferences = ExecutionPreferences(
    backend_preferences=ClassiqBackendPreferences(backend_name="aer_simulator")
)

qmod = set_execution_preferences(qmod, backend_preferences)

from classiq import set_execution_preferences from classiq.execution import ClassiqBackendPreferences, ExecutionPreferences backend_preferences = ExecutionPreferences( backend_preferences=ClassiqBackendPreferences(backend_name="aer_simulator") ) qmod = set_execution_preferences(qmod, backend_preferences)

In [ ]:

with open("max_clique.qmod", "w") as f:
    f.write(qmod)

with open("max_clique.qmod", "w") as f: f.write(qmod)

Synthesizing the QAOA Circuit and Solving the Problem¶

We can now synthesize and view the QAOA circuit (ansatz) used to solve the optimization problem:

In [ ]:

from classiq import show, synthesize

qprog = synthesize(qmod)
show(qprog)

from classiq import show, synthesize qprog = synthesize(qmod) show(qprog)

We now solve the problem using the generated circuit by using the execute method:

In [ ]:

from classiq import execute

res = execute(qprog).result()

from classiq import execute res = execute(qprog).result()

Optimization Results¶

We can also examine the statistics of the algorithm:

In [ ]:

import pandas as pd

optimization_result = pd.DataFrame.from_records(res[0].value)
optimization_result.sort_values(by="cost", ascending=False).head(5)

import pandas as pd optimization_result = pd.DataFrame.from_records(res[0].value) optimization_result.sort_values(by="cost", ascending=False).head(5)

Resulting Clique¶

In [ ]:

solution = optimization_result.solution[optimization_result.cost.idxmax()]
solution_nodes = [v for v in graph.nodes if solution[v]]
solution_edges = [
    (u, v) for u, v in graph.edges if u in solution_nodes and v in solution_nodes
]
nx.draw_kamada_kawai(graph, with_labels=True)
nx.draw_kamada_kawai(
    graph,
    with_labels=True,
    nodelist=solution_nodes,
    edgelist=solution_edges,
    node_color="r",
    edge_color="r",
)

solution = optimization_result.solution[optimization_result.cost.idxmax()] solution_nodes = [v for v in graph.nodes if solution[v]] solution_edges = [ (u, v) for u, v in graph.edges if u in solution_nodes and v in solution_nodes ] nx.draw_kamada_kawai(graph, with_labels=True) nx.draw_kamada_kawai( graph, with_labels=True, nodelist=solution_nodes, edgelist=solution_edges, node_color="r", edge_color="r", )

And the histogram:

In [ ]:

optimization_result.hist("cost", weights=optimization_result["probability"])

optimization_result.hist("cost", weights=optimization_result["probability"])

Lastly, we can compare to the classical solution of the problem:

Classical optimizer results¶

In [ ]:

from pyomo.opt import SolverFactory

solver = SolverFactory("couenne")
solver.solve(max_clique_model)

max_clique_model.display()

from pyomo.opt import SolverFactory solver = SolverFactory("couenne") solver.solve(max_clique_model) max_clique_model.display()

In [ ]:

solution = [int(pyo.value(max_clique_model.x[i])) for i in graph.nodes]
solution_nodes = [v for v in graph.nodes if solution[v]]
solution_edges = [
    (u, v) for u, v in graph.edges if u in solution_nodes and v in solution_nodes
]
nx.draw_kamada_kawai(graph, with_labels=True)
nx.draw_kamada_kawai(
    graph,
    with_labels=True,
    nodelist=solution_nodes,
    edgelist=solution_edges,
    node_color="r",
    edge_color="r",
)

solution = [int(pyo.value(max_clique_model.x[i])) for i in graph.nodes] solution_nodes = [v for v in graph.nodes if solution[v]] solution_edges = [ (u, v) for u, v in graph.edges if u in solution_nodes and v in solution_nodes ] nx.draw_kamada_kawai(graph, with_labels=True) nx.draw_kamada_kawai( graph, with_labels=True, nodelist=solution_nodes, edgelist=solution_edges, node_color="r", edge_color="r", )