QAOA 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.

MaxSetPacking problem#

max_set_packing_problem(sets)[source]#

Creates a QAOA problem instance with appropriate phase separator, mixer, and classical cost function.

Parameters:

setslist[set]: The sets for the problem instance.

Returns:

QAOAProblem: A QAOA problem instance for MaxSetPacking for given sets.

Example implementation#

from qrisp import QuantumVariable
from qrisp.qaoa import QAOAProblem, RZ_mixer, create_max_indep_set_cl_cost_function, create_max_indep_set_mixer, max_indep_set_init_function
import networkx as nx
from itertools import combinations

sets = [{0,7,1},{6,5},{2,3},{5,4},{8,7,0},{1}]

def non_empty_intersection(sets):
    return [(i, j) for (i, s1), (j, s2) in combinations(enumerate(sets), 2) if s1.intersection(s2)]

# create constraint graph
G = nx.Graph()
G.add_nodes_from(range(len(sets)))
G.add_edges_from(non_empty_intersection(sets))
qarg = QuantumVariable(G.number_of_nodes())

qaoa_max_indep_set = QAOAProblem(cost_operator=RZ_mixer,
                                mixer=create_max_indep_set_mixer(G),
                                cl_cost_function=create_max_indep_set_cl_cost_function(G),
                                init_function=max_indep_set_init_function)
results = qaoa_max_indep_set.run(qarg=qarg, depth=5)

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

cl_cost = create_max_indep_set_cl_cost_function(G)

print("5 most likely solutions")
max_five = sorted(results.items(), key=lambda item: item[1], reverse=True)[:5]
for res, prob in max_five:
    print([sets[index] for index, value in enumerate(res) if value == '1'], prob, cl_cost({res : 1}))