Mapping MAX-2-SAT to Ising model

Presenter:
The talk will be given by Marcin Wierzbiński
University of Warsaw, Faculty of Mathematics, Informatics and Mechanics, AstroCENT, Nicolaus Copernicus Astronomical Center, Polish Academy of Sciences.

Abstract:
Satisfiability is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In this case, we are considering logic formulas in a special form known as CNF (conjunctive normal form). The question is whether there are such values of variables for which the formula is true. 2-MAX-SAT is the problem of determining the maximum number of clauses in 2-CNF that can made true by assignment of truth values.

In this presentation, I will analyze 2-SAT and MAX-2-SAT computational problems in the context of quantum computations. I will describe the Ising model and express the MAX-2-SAT problem in this model. I will introduce the necessary definitions related to the above mentioned terminology. The computations were carried out using the D-Wave quantum annealer as well as two quantum simulators SimCim and Wildqat. In the experimental section, I will present the results of work on MAX-2-SAT problem.