QAOA E3Lin2#

Problem description#

Given a set of $m$ three-variable equations $A = {A_{j}}$ , over $n$ binary variables $x \in {0, 1}^{n}$ , where each equation $A_{j}$ is of the form $x_{a_{1, j}} + x_{a_{2, j}} + x_{a_{3, j}} = b_{j} mod 2$ , where $a_{1, j}, a_{2, j}, a_{3, j} \in [n]$ and $b_{j} \in {0, 1}$ , find an assignment $x \in {0, 1}^{n}$ that maximizes the number of satisfied equations.

Here, the equations are represented by a list of clauses, for example [0,1,3,1] corresponds to $[a_{1, j}, a_{2, j}, a_{3, j}, b_{j}]$ , that is, the equation

$x_{0} + x_{1} + x_{3} = 1 \mod 2$

Cost operator#

create_e3lin2_cost_operator(clauses)[source]#

Creates the cost operator for an instance of the E3Lin2 problem following Hadfield et al. The cost operator is given by $e^{- i γ H}$ where

H = \sum_{j = 1}^{m} H_{j}, H_{j} = (- 1)^{b_{j}} Z_{a_{1, j}} Z_{a_{2, j}} Z_{a_{3, j}}

Parameters:

clauseslist[list[int]]: The clasues defining the problem.

Returns:

function: A Python function receiving a QuantumVariable and real parameter $β$ . This function performs the application of the mixer associated to the graph $G$ .

Classical cost function#

create_e3lin2_cl_cost_function(clauses)[source]#

Creates the cost operator for an instance of the E3Lin2 problem.

Parameters:

clauseslist[list[int]]: The clasues defining the problem.

Returns:

cl_cost_functionfunction: The classical cost function for the problem instance, which takes a dictionary of measurement results as input.

E3Lin2 problem#

e3lin2_problem(clauses)[source]#

Creates a QAOA problem instance with appropriate phase separator, mixer, and classical cost function.

Parameters:

clauseslist[list[int]]: The clauses of the E3Lin2 problem instance.

Returns:

QAOAProblem: A QAOA problem instance for E3Lin2 for given clauses.

Example implementation#

from qrisp import QuantumVariable
from qrisp.qaoa import QAOAProblem, RX_mixer, create_e3lin2_cl_cost_function, create_e3lin2_cost_operator

clauses = [[0,1,2,1],[1,2,3,0],[0,1,4,0],[0,2,4,1],[2,4,5,1],[1,3,5,1],[2,3,4,0]]
num_variables = 6
qarg = QuantumVariable(num_variables)

qaoa_e3lin2 = QAOAProblem(cost_operator=create_e3lin2_cost_operator(clauses),
                           mixer=RX_mixer,
                           cl_cost_function=create_e3lin2_cl_cost_function(clauses))
results = qaoa_e3lin2.run(qarg=qarg, depth=5)

That’s it! Feel free to experiment with the init_type='tqa' option in the .run method for improved performance. In the following, we print the 5 most likely solutions together with their cost values.

cl_cost = create_e3lin2_cl_cost_function(clauses)

print("5 most likely solutions")
max_five = sorted(results.items(), key=lambda item: item[1], reverse=True)[:5]
for res, prob in max_five:
   print(res, prob, cl_cost({res : 1}))