Notebook

Max Cut¶

Definition¶

We are given an undirected graph with vertex set $V$ and edge set $E$.

Our aim is to partition the graph into two subgraphs connected by the maximum number of edges.

Applications¶

MaxCut is a ubiquitous problem in fields like Network Design, Statistical Physics, Very Large Scale Integration (VLSI), Circuit Layout Design, Data Clustering.

Path to solving the problem¶

MaxCut is a maximization problem and its cost function can be cast to an Ising problem through its respective Hamiltonian (see the Introduction and a reference),

$$ \displaystyle \large H = \displaystyle \textstyle\sum\limits_{uv \in E} s_{u} s_{v} $$

where $v, u \in V$ and $s_u$ is a spin variable, which is $1$ if vertex $u$ is in the one subgraph and $-1$ if it is in the other.

The myQLM allows us to encode a problem in this Hamiltonian form by using the MaxCut class with some specified graph. We can then create a job from the problem and send it to a Simulated Annealer (SA) wrapped with a Quantum Processing Unit (QPU) interface. The SA will minimize the Hamiltonian, hence we find the best solution to our problem.

In fact, the QLM contains an even more powerful solver $-$ Simulated Quantum Annealing (SQA). This quantum annealer has been tested on numerous benchmarks for the NP problems supported and produces results with a quality usually exceeding $98\%$. More details can be found in the documentation.

Quantum resources¶

To represent the problem as Ising, myQLM would need $N$ spins (one spin per vertex).

Example problem¶

Imagine we are given a tree graph with $30$ vertices and $29$ edges, as shown below (left). One may quickly figure that we can partition the graph into two subgraphs, connected by all the graph edges. To achieve this, we can simply colour the nodes on the even levels of the tree graph by one colour, and the nodes on the odd levels $-$ by the other (right).

Let us now describe how one can reach this answer using tools from myQLM. Furthermore, the approach will be applicable to finding the MaxCut of any graph!

We will start by specifying the graph with the networkx library, which allows us to explore a huge variety of graphs.

In [ ]:

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

# Specify the graph 
graph = nx.full_rary_tree(2, 30)

# Draw the graph - may take time for bigger graphs
nodes_positions = nx.spring_layout(graph, iterations=len(graph.nodes()) * 100)
plt.figure(figsize=(14, 9))
nx.draw_networkx(graph, 
                 pos=nodes_positions, 
                 node_color='#4EEA6A', 
                 node_size=440, 
                 font_size=14)
plt.show()

The MaxCut class can now be called with this graph as input.

In [ ]:

from qat.opt import MaxCut

max_cut_problem = MaxCut(graph)

Solution¶

Resolution of the problem using a BatchGenerator¶

A high level solver of the MaxCut problem is available in the QLM under the form of a BatchGenerator called MaxCutGenerator. It is designed as simple interface to solve the problem on an input graph, while hiding the complexities of the underlying algorithms.

The different resolution methods that can be selected are "qaoa" (for QAOA Circuit Generation), "annealing" (for Simulated Quantum Annealing), and "schedule" (for Analog Quantum Scheduler Generation). A user-interpretable result is returned from the job execution, where the two resulting partitions of the nodes and the number of edges cut can be retrieved from the subsets and cost attribute respectively. A display method is also provided by the result object to visualize the partitioning of the graph.

An example of using the batch generator to generate a quantum annealing job and executing it with SimulatedAnnealing is provided below.

In [ ]:

from qat.generators import MaxCutGenerator
from qat.qpus import SimulatedAnnealing
from qat.core import Variable

# 1. Extract parameters for SA
problem_parameters_dict = max_cut_problem.get_best_parameters()
n_steps = problem_parameters_dict["n_steps"]
temp_max = problem_parameters_dict["temp_max"]
temp_min = problem_parameters_dict["temp_min"]

# 2. Create a temperature schedule and a QPU
tmax = 1.0
t = Variable("t", float)
temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)

max_cut_application = MaxCutGenerator(job_type="sqa") | SimulatedAnnealing(temp_t=temp_t, n_steps=n_steps)
combinatorial_result = max_cut_application.execute(graph)

print("The nodes in the first subgraph are", combinatorial_result.subsets[0])
print("The nodes in the second subgraph are", combinatorial_result.subsets[1])
# The cost here is negative since all combinatorial optimization problems are defined as a minimization problem, so a factor of -1 is needed
print("The number of edges that are cut is", -1 * combinatorial_result.cost)

combinatorial_result.display(with_figure=True, figsize=(14, 9), node_size=440, font_size=14, pos=nodes_positions)

Simulated Annealing¶

If we want to solve the problem with SA straight, we can still do so via the following steps:

Extract some fine-tuned parameters for MaxCut (found for SQA) which are needed for the temperature schedule.
Create the temperature schedule using the t time variable (instance of the class Variable) and thus the SimulatedAnnealing QPU.
Create a job from the problem by calling the to_job() method and send it to the QPU.
Extract the Result and present the solution spin configuration.
Draw the respective nodes of each subgraph.

Each spin from the solution configuration corresponds to a node from the graph at the same position. Note that if the numbering of the input nodes starts from $1$ and not from $0$, one still needs to look at the $0$th spin to extract information for this first node, numbered as $1$.

When a spin has the value of $1$ or $-1$, this means that the respective node belongs to the one or the other subgraph.

In [ ]:

from qat.qpus import SimulatedAnnealing
from qat.simulated_annealing import integer_to_spins
from qat.core import Variable

# 1. Extract parameters for SA
problem_parameters_dict = max_cut_problem.get_best_parameters()
n_steps = problem_parameters_dict["n_steps"]
temp_max = problem_parameters_dict["temp_max"]
temp_min = problem_parameters_dict["temp_min"]

# 2. Create a temperature schedule and a QPU
tmax = 1.0
t = Variable("t", float)
temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)
sa_qpu = SimulatedAnnealing(temp_t=temp_t, n_steps=n_steps)

# 3. Create a job and send it to the QPU
problem_job = max_cut_problem.to_job('sqa', tmax=tmax)
problem_result = sa_qpu.submit(problem_job)

# 4. Extract and print solution configuration
state = problem_result.raw_data[0].state.int  # raw_data is a list of Samples - one per computation
solution_configuration = integer_to_spins(state, len(graph.nodes()))
print("Solution configuration: \n" + str(solution_configuration) + "\n")
indices_spin_1 = np.where(solution_configuration == 1)[0]
print("The nodes in the first subgraph:\n" + str(indices_spin_1) + "\n")
indices_spin_minus_1 = np.where(solution_configuration == -1)[0]
print("The nodes in the second subgraph:\n" + str(indices_spin_minus_1))

# 5. Draw the coloured subgraphs - may take longer for larger graphs
plt.figure(figsize=(14, 9))
node_size = 440
font_size = 14
nx.draw_networkx(graph, 
                 pos=nodes_positions, 
                 nodelist=indices_spin_1.tolist(), 
                 node_color='#FFE033', 
                 node_size=node_size, 
                 font_size=font_size)

nx.draw_networkx(graph, 
                 pos=nodes_positions, 
                 nodelist=indices_spin_minus_1.tolist(), 
                 node_color='#7B9BF2', 
                 node_size=node_size, 
                 font_size=font_size)

nx.draw_networkx_edges(graph, pos=nodes_positions)
plt.show()

Solution analysis¶

We are interested in how well the partitioning went. We know that for a tree, the number of connecting edges should be all edges. So we can compare this to the number of edges between the nodes we coloured.

In [ ]:

number_of_edges_connecting_subgraphs = 0
for (u, v) in graph.edges():
    if solution_configuration[u] * solution_configuration[v] == (-1):
        number_of_edges_connecting_subgraphs += 1

print("For a MaxCut partitioned tree graph the number of connecting edges is:")
print(len(graph.edges()))

print("Number of edges, which connect the two partitioned subgraphs:")
print(number_of_edges_connecting_subgraphs)