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_sqa_initial_parameters()
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"]
nbshots = problem_parameters_dict['nbshots']
n_steps = problem_parameters_dict['n_steps']
n_trotters = problem_parameters_dict['n_trotters']

# 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=nbshots)
sqa_qpu = SQAQPU(temp_t=temp_t, n_steps=n_steps, n_trotters=n_trotters, seed=999)
problem_result = sqa_qpu.submit(problem_job)

# Sample analysis
Q = kclique_problem.q_matrix
offset= kclique_problem.offset_q
energies = []
best_state = 0
for sample in problem_result: # raw_data is a list of Samples - one per shot
    x = np.array([int(b) for b in sample.state.bitstring])
    energy = -x.T @ Q @ x - offset
    energies.append(energy)
    if energy <= min(energies):
        best_state= sample.state.int

# Extract and print solution configuration
solution_configuration = integer_to_spins(best_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:
[2 3 4]

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