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:
clauseslist[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:
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}))