KClique

Given an undirected graph with vertex set \(V\) and edge set \(E\), the problem consists in finding out whether there exists a complete subgraph of size \(K\). Annealing the problem with the help of our KClique class (or KCliqueGenerator class) requires \(\#V\) spins (one spin per 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 KClique
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(5))
graph.add_edges_from([(0, 1), (0, 2), (0, 3), (0, 4),
                    (0, 5), (1, 2), (1, 5)])

# Specify the size of the desired subgraph
K = 3
# Impose constraints for the right encoding
B = 1
A = B * K + 1
kclique_problem = KClique(graph, K, A, B)

# Extract parameters for SA
problem_parameters_dict = kclique_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 = kclique_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")
indices_spin_1 = np.where(solution_configuration == 1)[0]
print("The nodes of the complete subgraph are:\n" + str(indices_spin_1) + "\n")

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

The nodes of the complete subgraph are:
[0 1 2]

<stdin>:34: UserWarning: If SQAQPU is used, gamma_t will be needed.

This example is also detailed in this notebook on solving K-Clique problems with SA.