> ## Documentation Index
> Fetch the complete documentation index at: https://docs.classiq.io/llms.txt
> Use this file to discover all available pages before exploring further.

# Max Clique Problem

> **[View on GitHub](https://github.com/Classiq/classiq-library/blob/main/applications/optimization/max_clique/max_clique.ipynb)**
>
> Open this notebook in GitHub to run it yourself

This tutorial solves the max clique problem in graph theory using Classiq.

A clique is a subset of vertices in a graph such that each pair is adjacent to one other.

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

## Defining the Optimization Problem

Encode each node as a binary variable:

```python theme={null}
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:

```python theme={null}
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)
```

![output](https://mintcdn.com/classiq/tcPvHr2JZgblscSZ/explore/applications/optimization/max_clique/max_clique_files/max_clique_1.png?fit=max\&auto=format\&n=tcPvHr2JZgblscSZ\&q=85\&s=622cdfc00831043a4f9e28d1b7193d00)

## Setting Up the Classiq Problem Instance

To solve the Pyomo model defined above, use the `CombinatorialProblem` Python class.

Under the hood, it translates the Pyomo model to a quantum model of the Quantum Approximate Optimization Algorithm (QAOA) \[[1](#qaoa)], with a cost Hamiltonian translated from the Pyomo model.

Choose the number of layers for the QAOA ansatz using the `num_layers` argument:

```python theme={null}
from classiq import *
from classiq.applications.combinatorial_optimization import CombinatorialProblem

combi = CombinatorialProblem(pyo_model=max_clique_model, num_layers=3)

qmod = combi.get_model()
```

## Synthesizing the QAOA Circuit and Solving the Problem

Synthesize and view the QAOA circuit (ansatz) used to solve the optimization problem:

```python theme={null}
qprog = combi.get_qprog()
show(qprog)
```

> [!NOTE]
>
> **Output:**
>
> ```
>
> Quantum program link: https://platform.classiq.io/circuit/3IjIaCrRQiB3S9Ap4xuNs17zzBo
>
>
> ```

> [!NOTE]
>
> **Output:**
>
> ```
> https://platform.classiq.io/circuit/3IjIaCrRQiB3S9Ap4xuNs17zzBo?login=True&version=22
>
>
> ```

Solve the problem by calling the `optimize` method of the `CombinatorialProblem` object.

For the classical optimization part of the QAOA algorithm, define the maximum number of classical iterations (`maxiter`) and the $\alpha$-parameter (`quantile`) for running CVaR-QAOA, an improved variation of the QAOA algorithm \[[2](#cvar)]:

```python theme={null}
optimized_params = combi.optimize(maxiter=50, quantile=0.7)
```

> [!NOTE]
>
> **Output:**
>
> ```
> /home/dor/Sources/Classiq/library-13/lib/python3.13/site-packages/classiq/applications/combinatorial_optimization/combinatorial_problem.py:258: ClassiqDeprecationWarning: ExecutionSession.minimize is deprecated; use variational_minimize instead.
>     result = _es.minimize(
>
>
> ```

```python theme={null}
import matplotlib.pyplot as plt

plt.plot(combi.cost_trace)
plt.xlabel("Iterations")
plt.ylabel("Cost")
plt.title("Cost convergence")
```

> [!NOTE]
>
> **Output:**
>
> ```
>
> Text(0.5, 1.0, 'Cost convergence')
>
>
> ```

![output](https://mintcdn.com/classiq/tcPvHr2JZgblscSZ/explore/applications/optimization/max_clique/max_clique_files/max_clique_2.png?fit=max\&auto=format\&n=tcPvHr2JZgblscSZ\&q=85\&s=e79844c7f58b99be7c11bfa79e04229c)

## Viewing the Optimization Results

Examine the statistics of the algorithm.

The optimization is always defined as a minimization problem, so the Pyomo-to-Qmod translator changes the positive maximization objective to negative minimization.

To get samples with the optimized parameters, call the `sample` method:

```python theme={null}
optimization_result = combi.sample(combi.optimized_params)
optimization_result.sort_values(by="cost").head(5)
```

| | solution | probability | cost |
| - | - | - | - |
| 43 | \{'x': \[0, 1, 1, 1, 0, 1, 0]} | 0.007812 | -4 |
| 45 | \{'x': \[1, 1, 1, 1, 0, 0, 0]} | 0.007324 | -4 |
| 12 | \{'x': \[0, 1, 1, 0, 0, 1, 0]} | 0.018066 | -3 |
| 13 | \{'x': \[1, 0, 1, 1, 0, 0, 0]} | 0.018066 | -3 |
| 31 | \{'x': \[0, 1, 0, 1, 0, 1, 0]} | 0.010742 | -3 |

Compare the optimized results to uniformly sampled results:

```python theme={null}
uniform_result = combi.sample_uniform()
```

And compare the histograms:

```python theme={null}
optimization_result["cost"].plot(
    kind="hist",
    bins=40,
    edgecolor="black",
    weights=optimization_result["probability"],
    alpha=0.6,
    label="optimized",
)
uniform_result["cost"].plot(
    kind="hist",
    bins=40,
    edgecolor="black",
    weights=uniform_result["probability"],
    alpha=0.6,
    label="uniform",
)
plt.legend()
plt.ylabel("Probability", fontsize=16)
plt.xlabel("cost", fontsize=16)
plt.tick_params(axis="both", labelsize=14)
```

![output](https://mintcdn.com/classiq/tcPvHr2JZgblscSZ/explore/applications/optimization/max_clique/max_clique_files/max_clique_3.png?fit=max\&auto=format\&n=tcPvHr2JZgblscSZ\&q=85\&s=d7cbf300e5fb110ee85dec0268f53e5d)

Plot the solution:

```python theme={null}
best_solution = optimization_result.solution[optimization_result.cost.idxmin()]
best_solution
```

> [!NOTE]
>
> **Output:**
>
> ```
> {'x': [0, 1, 1, 1, 0, 1, 0]}
>
>
> ```

```python theme={null}
solution_nodes = [v for v in graph.nodes if best_solution["x"][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",
)
```

![output](https://mintcdn.com/classiq/tcPvHr2JZgblscSZ/explore/applications/optimization/max_clique/max_clique_files/max_clique_4.png?fit=max\&auto=format\&n=tcPvHr2JZgblscSZ\&q=85\&s=3062ec3187659c9a15c55631f943d2d7)

## Comparing to a Classical Solver

Lastly, compare to the classical solution of the problem:

```python theme={null}
from pyomo.opt import SolverFactory

solver = SolverFactory("couenne")
solver.solve(max_clique_model)
classical_solution = [
    int(pyo.value(max_clique_model.x[i])) for i in range(len(max_clique_model.x))
]
print("Classical solution:", classical_solution)
```

> [!NOTE]
>
> **Output:**
>
> ```
>
> Classical solution: [1, 1, 1, 1, 0, 0, 0]
>
>
> ```

```python theme={null}
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",
)
```

![output](https://mintcdn.com/classiq/tcPvHr2JZgblscSZ/explore/applications/optimization/max_clique/max_clique_files/max_clique_5.png?fit=max\&auto=format\&n=tcPvHr2JZgblscSZ\&q=85\&s=b60a0aebb2e7d8bacc94a6e20c0e6868)

## References

\[1] [Farhi, Edward, Jeffrey Goldstone, and Sam Gutmann. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.](https://arxiv.org/abs/1411.4028)

\[2] [Barkoutsos, Panagiotis Kl, et al. (2020). Improving variational quantum optimization using CVaR. Quantum 4: 256.](https://arxiv.org/abs/1907.04769)


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.