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 \text{ 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\gamma H}$ where

\[H=\sum_{j=1}^m H_j,\qquad H_j=(-1)^{b_j}Z_{a_{1,j}}Z_{a_{2,j}}Z_{a_{3,j}}\]

Parameters:

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

Returns:

function: A Python function receiving a QuantumVariable and real parameter $\beta$. 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:

clasueslist[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, e3lin2_init_function

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