QIRO MaxSetPacking#

Problem description#

Given a universe $[n]$ and $m$ subsets $S = (S_{j})_{j = 1}^{m}$ , $S_{j} \subset [n]$ , find the maximum cardinality subcollection $S^{'} \subset S$ of pairwise disjoint subsets. Following the work of Hadfield et al., the MaxSetPacking problem is solved by solving the MaxIndepSet problem on the constraint graph $G = (V, E)$ where vertices correspond to subsets in $S$ and edges correspond to pairs of intersecting subsets.

Transformation to MIS#

transform_max_set_pack_to_mis(problem)[source]#

Transforms a Maximum Set Packing problem instance into a Maximum Independent Set (MIS) problem instance.

Parameters:

problemlist[set]: A list of sets specifying the problem.

Returns:

Gnx.Graph: The corresponding graph to be solved by an MIS implementation.

Example implementation#

from qrisp import QuantumVariable
from qrisp.qiro import QIROProblem, create_max_indep_replacement_routine, create_max_indep_cost_operator_reduced, qiro_rx_mixer, qiro_init_function
from qrisp.qaoa import create_max_indep_set_cl_cost_function
import matplotlib.pyplot as plt
import networkx as nx

# sets are given as list of sets
sets = [{0,7,1},{6,5},{2,3},{5,4},{8,7,0},{2,4,7},{1,3,4},{7,9},{1,9},{1,3,8},{4,9},{0,7,9},{0,4,8},{1,4,8}]

G = transform_max_set_pack_to_mis(sets)
qarg = QuantumVariable(G.number_of_nodes())

qiro_instance = QIROProblem(G,
                            replacement_routine=create_max_indep_replacement_routine,
                            cost_operator=create_max_indep_cost_operator_reduced,
                            mixer=qiro_rx_mixer,
                            cl_cost_function=create_max_indep_set_cl_cost_function,
                            init_function=qiro_init_function
                            )
res_qiro = qiro_instance.run_qiro(qarg=qarg, depth=3, n_recursions=2)

That’s it! In the following, we print the 5 most likely solutions together with their cost values, and compare to the NetworkX solution.

cl_cost = create_max_indep_set_cl_cost_function(G)

print("5 most likely QIRO solutions")
max_five_qiro = sorted(res_qiro, key=res_qiro.get, reverse=True)[:5]
for res in max_five_qiro:
    print([sets[index] for index, value in enumerate(res) if value == '1'])
    print(cl_cost({res : 1}))

print("Networkx solution")
print([sets[index] for index in nx.approximation.maximum_independent_set(G)])