QAOA MinSetCover#

Problem description#

Given a universe \([n]\) and \(m\) subsets \(\mathcal S = (S_j)^m_{j=1}\) , \(S_j \subset [n]\) find the minimum cardinality subcollection \(\mathcal S' \subset \mathcal S\) of the \(S_j\) such that their union recovers \([n]\). The QAOA implementation is based on the work of Hadfield et al.

Mixer#

create_min_set_cover_mixer(sets, universe)[source]#

Creates the controlled_RX_mixer for an instance of the minimum set cover problem following Hadfield et al.

The belonging predicate function indicates if a set can be swapped out of the solution.

Parameters:

setslist[set]: A list of sets.
universeset: The union of all sets.

Returns:

function: A Python function receiving a QuantumVariable and real parameter \(\beta\). This function performs the application of the mixer associated to the problem instance.

Classical cost function#

create_min_set_cover_cl_cost_function(sets, universe)[source]#

Creates the classical cost function for an instance of the minimum set cover problem.

Parameters:

setslist[set]: A list of sets.
universeset: The union of all sets.

Returns:

cl_cost_functionfunction: The classical cost function for the problem instance, which takes a dictionary of measurement results as input.

Initial state function#

min_set_cover_init_function(qv)[source]#

Prepares the initial state \(\ket{1}^{\otimes n}\).

Parameters:

qvQuantumVariable: The quantum argument.

MinSetCover problem#

min_set_cover_problem(sets, universe)[source]#

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

Parameters:

setslist[set]: A list of sets.
universeset: The union of all sets.

Returns:

QAOAProblem: A QAOA problem instance for MinSetCover for given sets and universe.

Example implementation#

from qrisp import QuantumVariable
from qrisp.qaoa import QAOAProblem, RZ_mixer, create_min_set_cover_mixer, create_min_set_cover_cl_cost_function, min_set_cover_init_function

sets = [{0,1,2,3},{1,5,6,4},{0,2,6,3,4,5},{3,4,0,1},{1,2,3,0},{1}]
universe = set.union(*sets)
qarg = QuantumVariable(len(sets))

qaoa_min_set_cover = QAOAProblem(cost_operator=RZ_mixer,
                                 mixer= create_min_set_cover_mixer(sets, universe),
                                 cl_cost_function=create_min_set_cover_cl_cost_function(sets, universe),
                                 init_function=min_set_cover_init_function)
results = qaoa_min_set_cover.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_min_set_cover_cl_cost_function(sets, universe)

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}))