QAOA MaxSetPacking 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 pairwise disjoint subsets.

Cost operator

maxSetPackCostOp(sets, universe)

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 for mcx-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 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 the operators

>>> cost_fun = maxSetPackclCostfct(sets=sets,universe=sol)
>>> mixerOp = RZ_Mixer()
>>> costOp = maxSetPackCostOp(sets=sets, universe=sol)

Classical cost function

maxSetPackclCostfct(sets, universe)

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)

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