QAOA MaxSetPacking#
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 pairwise disjoint subsets.
Cost operator#
- maxSetPackCostOp(problem)[source]#
- Create the cost/problem operator for this problem instance. The swapping rule is to swap a set in and out of the solution, if it is not intersecting with any other set.Idea - Per set:
Create ancillas for every element, they represent these elements
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
formcx
-operation) we set this ancilla to “1”
Then perform mcx on the qubit describing the set as follows:If all ancillas are “1” this means the qubits describing the sets contain no intersections with the considered set. We can then swap the set in (or out).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 by the amount of elements (+1, since its 0-indexed)>>> sets = [[0,7,1],[6,5],[2,3],[5,4],[8,7,0],[1]] >>> sol = 9 >>> problem = [sol, sets]
The relations between the sets, i.e. which vertice is in which other sets
>>> print(get_neighbourhood_relations(sets, len_universe=len(sol)))
Assign the operators
>>> cost_fun = maxSetPackclCostfct(problem) >>> mixerOp = RZ_mixer >>> costOp = maxSetPackCostOp(problem)
Classical cost function#
Helper function#
- get_neighbourhood_relations(problem)[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:
- problemList
The problem definition, as described above
- 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.maxSetPackInfrastr import maxSetPackclCostfct,maxSetPackCostOp, get_neighbourhood_relations, init_state
from qrisp import QuantumVariable
# sets are given as list of lists
sets = [[0,7,1],[6,5],[2,3],[5,4],[8,7,0],[1]]
# full universe is given as a tuple
sol = (0,1,2,3,4,5,6,7,8)
# the realtions between the sets, i.e. with vertice is in which other sets
print(get_neighbourhood_relations(sets, len_universe=len(sol)))
# assign the operators
cost_fun = maxSetPackclCostfct(sets=sets,universe=sol)
mixerOp = RZ_mixer()
costOp = maxSetPackCostOp(sets=sets, universe=sol)
#initialize the qarg
qarg = QuantumVariable(len(sets))
# run the 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)
# assign the cost_func
def testCostFun(state, universe):
list_universe = [True]*len(universe)
temp = True
obj = 0
intlist = [s for s in range(len(list(state))) if list(state)[s] == "1"]
sol_sets = [sets[index] for index in intlist]
for seto in sol_sets:
for val in seto:
if list_universe[val]:
list_universe[val] = False
else:
temp = False
break
if temp:
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))