QAOA MinSetCover problem implementation#

Problem description#

Given a universe \([n]\) and \(m\) subsets \(S = (S_j)^m_{j=1}\) , \(S_j \subset [n]\) find the maximum cardinality subcollection \(S' \subset S\) of the \(S_j\) such that their union recovers \([n]\) .

Cost operator#

minSetCoverCostOp(sets, universe)[source]#
Create the cost/problem operator for this problem instance. Swapping rule is to swap a set in and out of the solution, if all elements are covered by other sets
Idea - Per set:

  • create ancillas for every element, they represent these elements

  • ancillas are set to “1” by default

  • perform multi controlled x operations on each ancilla

  • controls are given by sets with also contain the considered element

  • if all controls are “0” (see ctrl_state for mcx-operation) we set this ancilla to “0”

Then perform mcx on the qubit describing the set:
If all ancillas are “1” this means that, for all elements in the list, there is already (atleast) one set in the bitstring describing the solution sets, which already contains this element. The set can then be swapped in (or out) of the solution, since all elements are covered by other sets
Afterwards uncompute the ancillas
Parameters
setslist(Lists)

The sets the universe is seperated into as by the problem definition

universe: Tuple

The universe for the problem instance, i.e. all possible values (all graph vertices)

Returns
QuantumCircuit: qrisp.QuantumCircuit

the Operator applied to the circuit-QuantumVariable

Examples

Definition of the sets, given as list of lists. Full universe sol is given as a tuple >>> sets = [[0,7,1],[6,5],[2,3],[5,4],[8,7,0],[1]] >>> sol = (0,1,2,3,4,5,6,7,8)

The relations between the sets, i.e. which vertice is in which other sets

>>> print(get_neighbourhood_relations(sets, len_universe=len(sol)))

Assign operators >>> cost_fun = minSetCoverclCostfct(sets=sets,universe = sol) >>> mixerOp = RZ_Mixer() >>> costOp = minSetCoverCostOp(sets=sets, universe=sol)

Classical cost function#

minSetCoverclCostfct(sets, universe)[source]#

create the classical cost function for the problem instance

Parameters
setslist(Lists)

The sets the universe is seperated into as by the problem definition

universe: Tuple

The universe for the problem instance, i.e. all possible values (all graph vertices)

Returns
Costfunctionfunction

the classical function for the problem instance, which takes a dictionary of measurement results as input

Helper function#

get_neighbourhood_relations(sets, len_universe)[source]#

helper function to return a dictionary describing neighbourhood relations in the sets, i.e. for each element in the universe, gives the info in which the element is contained in.

Parameters
setslist(Lists)

The sets the universe is seperated into as by the problem definition

len_universe: int

The number of elements in the universe

Returns
neighbourhood relation dictionarydict
keys: all universe elements (all graph vertices)
values: per universe element the sets it is contained in

Full example implementation:#

from qrisp.qaoa import QAOAProblem
from qrisp.qaoa.mixers import RZ_mixer
from qrisp.qaoa.problems.minSetCoverInfrastr import minSetCoverclCostfct,minSetCoverCostOp, init_state

from qrisp import QuantumVariable

# sets are given as list of lists
sets = [[0,1,2,3],[1,5,6,4],[0,2,6,3,4,5],[3,4,0,1],[1,2,3,0],[1]]
# full universe is given as a tuple
sol = (0,1,2,3,4,5,6)

# assign operators
cost_fun = minSetCoverclCostfct(sets=sets,universe = sol)
mixerOp = RZ_mixer()
costOp = minSetCoverCostOp(sets=sets, universe=sol)

#initialize variable
qarg = QuantumVariable(len(sets))

#+run qaoa
QAOAinstance = QAOAProblem(cost_operator=costOp ,mixer= mixerOp, cl_cost_function=cost_fun)
QAOAinstance.set_init_function(init_function=init_state)
InitTest = QAOAinstance.run(qarg=qarg, depth=5)

# create example cost_func
def testCostFun(state,universe):
   obj = 0
   intlist = [s for s in range(len(list(state))) if list(state)[s] == "1"]
   sol_sets = [sets[index] for index in intlist]
   res = ()
   for seto in sol_sets:
      res = tuple(set(res+ seto))
   if res == universe:
      obj -= len(intlist)

   return obj


# print the most likely solutions
print("5 most likely Solutions")
maxfive = sorted(InitTest, key=InitTest.get, reverse=True)[:5]
for res, val in InitTest.items():
   if res in maxfive:
      print((res, val))
      print(testCostFun(res, universe=sol))