Graph Partitioning

Given an undirected graph with vertex set \(V\) and edge set \(E\), the problem consists in partitioning the graph into two equally-sized subgraphs connected by the minimal number of edges. Annealing the problem with the GraphPartitioning class (or GraphPartitioningGenerator class) needs \(\#V\) spins (one spin for each individual vertex).

Solving this problem using the simulated annealing method requires the SimulatedAnnealing QPU.

import networkx as nx
import numpy as np
from qat.opt import GraphPartitioning
from qat.qpus import SimulatedAnnealing
from qat.simulated_annealing import integer_to_spins
from qat.core import Variable

# Specify the graph
graph = nx.Graph()
graph.add_nodes_from(np.arange(10))
graph.add_edges_from([(0, 1), (0, 4), (0, 6), (1, 2), (1, 4),
                    (1, 7), (2, 3), (2, 5), (2, 8), (3, 5),
                    (3, 9), (4, 6), (4, 7), (5, 8), (5, 9),
                    (6, 7), (7, 8), (8, 9)])

# Impose constraints for the right encoding
B = 1
A = B + 0.1
graph_partitioning_problem = GraphPartitioning(graph, A, B=B)

# Extract parameters for SA
problem_parameters_dict = graph_partitioning_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"]

# 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)

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

# Extract and print the 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")

# Show nodes of subgraphs
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))

Solution configuration: 
[-1. -1.  1.  1. -1.  1. -1. -1.  1.  1.]

The nodes in the first subgraph:
[2 3 5 8 9]

The nodes in the second subgraph:
[0 1 4 6 7]
<stdin>:34: UserWarning: If SQAQPU is used, gamma_t will be needed.

This example is also detailed in this notebook on solving Graph Partitioning problems with SA.