QAOA MinSetCover#
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 setsIdea - 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
formcx
-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 setsAfterwards 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))