QAOA MaxSat#
Problem description#
Given \(m\) disjunctive clauses over \(n\) Boolean variables \(x\) , where each clause contains at most \(l \geq 2\) literals, find a variable assignment that maximizes the number of satisfied clauses.
Cost operator#
- maxSatCostOp(problem)[source]#
- Implementation for MaxSat Cost-Operator, in accordance to the original QAOA-paper.For each clause \(C_i\) apply \(C_i(x) = 1 - \prod_j x_j\) (replace \(x_j\) with
\((1-x_j)\) if \(x_j\) is negated). The problem operator is acquired with the substitution \(x_j = (I - Z_j)\) , where \(Z_j\) is the Pauli- \(Z\) operator applied to the \(j\) -th qubit.
- Parameters:
- clausesList(Lists)
Clauses to be considered for MaxSat. Should be given as a list of lists and 1-indexed instead 0-indexed, see example
- Returns:
- QuantumCircuit: qrisp.QuantumCircuit
the Operator applied to the circuit-QuantumVariable
Examples
>>> clauses11 = (6, [[1,2,-3], [1,4,-6], [4,5,6], [1,3,-4], [2,4,5], [1,3,5], [-2,-3,6]])
Explanation:First entry of tuple is the number of variables, second is the clausesClause [1, 2, -4] is fulfilled by the QuantumStates “1100”, “1110”if the sign is positive : the index has of the QuantumVariable to be “1”, if negative sign the index has to be “0”.
indices not mentioned can be “0” or “1” (the third integer in this case).
start with 1 in your clauses! because
int 0
has no sign and this is problematic.we want to keep the mathematical formulation, so no handing over strings!
Assign the operators
>>> cost_operator=maxSatCostOp(clauses11), >>> mixer=RX_mixer
Classical cost function#
Helper function#
- clausesdecoder(problem)[source]#
Decodes the clause arrays to represent binary bitstrings, that fulfill the clauses –> used to calculate objective function, i.e. the classical cost function
- Parameters:
- clausesList(List)
clauses to be considered for maxSat (! 1-indexed, instead of 0-indexed, see example above)
- numVarsint
the total amount of Variables considered within the clauses
- Returns:
- decodedClausesIterable(tuple)
clauses as bitstrings, to be compared to the QAOA-bitstring results
Examples
As above:
>>> clauses11 = [[1,2,-3], [1,4,-6], [4,5,6], [1,3,-4], [2,4,5], [1,3,5], [-2,-3,6]] >>> decodedClauses = clausesdecoder( clauses = clauses11, numVars = 6)
Assign
cost_function
>>> cl_cost_function=maxSatclCostfct(decodedClauses)
Full example implementation:#
from qrisp.qaoa import QAOAProblem
from qrisp.qaoa.problems.maxSatInfrastr import maxSatclCostfct, maxSatCostOp, clausesdecoder, init_state
from qrisp.qaoa.mixers import RX_mixer
from qrisp import QuantumVariable
clauses11 = [[1,2,-3],[1,4,-6], [4,5,6],[1,3,-4],[2,4,5],[1,3,5],[-2,-3,6]]
#Clauses are decoded, s.t. the Cost-Optimizer can read them
#numVars is the amount of considered variables, i.e. highest number (= Number of Qubits in Circuit aswell)
decodedClauses = clausesdecoder( clauses = clauses11, numVars = 6)
#print(decodedClauses)
qarg = QuantumVariable(len(clauses11))
#CostOperator-Generator has to be called with the clauses
#CostFct-Generator has to be called with decodedClauses
QAOAinstance = QAOAProblem(cost_operator=maxSatCostOp(clauses11), mixer=RX_mixer, cl_cost_function=maxSatclCostfct(decodedClauses))
QAOAinstance.set_init_function(init_function=init_state)
theNiceQAOA = QAOAinstance.run(qarg=qarg, depth=5)
#print the ideal solutions
print("5 most likely Solutions")
maxfive = sorted(theNiceQAOA, key=theNiceQAOA.get, reverse=True)[:5]
for res, val in theNiceQAOA.items():
if res in maxfive:
print((res, val))
print(clCostfct({res : 1}))
print("Final energy value and associated solution values")
costfct = maxSatclCostfct(decodedClauses)
print(costfct(theNiceQAOA))
#Final Result-dictionary
resDict = dict()
for index in decodedClauses:
for index2 in index:
if index2 in resDict.keys():
resDict[index2] +=1
else:
resDict[index2] =1
print(resDict)