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 quantum annealing method requires SQAQPU.

import networkx as nx
import numpy as np
from qat.opt import KClique
from qat.qpus import SQAQPU
from qat.core import Variable
from qat.core.spins import integer_to_spins

# 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 SQA
problem_parameters_dict = kclique_problem.get_best_parameters()
n_monte_carlo_updates = problem_parameters_dict["n_monte_carlo_updates"]
n_trotters = problem_parameters_dict["n_trotters"]
n_steps = int(n_monte_carlo_updates /
            (n_trotters * len(graph.nodes()))) # the last one is the number of spins, i.e. the problem size
temp_max = problem_parameters_dict["temp_max"]
temp_min = problem_parameters_dict["temp_min"]
gamma_max = problem_parameters_dict["gamma_max"]
gamma_min = problem_parameters_dict["gamma_min"]

# Create a temperature and a gamma schedule
tmax = 1.0
t = Variable("t", float)
temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)
gamma_t = gamma_min * (t / tmax) + gamma_max * (1 - t / tmax)

# Create a job and send it to a QPU
problem_job = kclique_problem.to_job('sqa', gamma_t=gamma_t, tmax=tmax, nbshots=1)
sqa_qpu = SQAQPU(temp_t=temp_t, n_steps=n_steps, n_trotters=n_trotters)
problem_result = sqa_qpu.submit(problem_job)

# Present best configuration
state_int = problem_result.raw_data[0].state.int  # raw_data is a list of Samples - one per shot
solution_configuration = integer_to_spins(state_int, 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]

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