Department of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
•    understand and discuss current problems in quantum informatics,
•    discuss new quantum computing technologies,
•    exchange ideas and research results,
•    integrate information across different research teams,
•    build a community around quantum informatics.
Venue:  via Internet, Webex

Tuesday, 15th of December, 2020, 9:30-11:00

Marcin Wierzbiński -  University of Warsaw, Faculty of Mathematics, Informatics and Mechanics,AstroCENT, Nicolaus Copernicus Astronomical Center, Polish Academy of Sciences

Topic: Mapping MAX-2-SAT to Ising model



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.



[1] Santra, Siddhartha et al. "Max 2-SAT with up to 108 Qubits." {New Journal of Physics 16.4} (2014): 045006. Crossref. Web.
[2] Egor S. Tiunov, Alexander E. Ulanov, A. I. Lvovsky "Annealing by simulating the coherent Ising machine" (2019) {Optics Express}
[3] "Mario Ziman, Teiko Heinosaari "The mathematical language of quantum theory" {Cambridge University Press}

  • 3 years, 6 months ago