Zapraszamy na Krakow Quantum Informatics Seminar organizowane wspólnie przez Katedrę Informatyki AGH i IBM Software Lab Kraków. Spotkanie odbędzie się we wtorek 15.12.2020 w godzinach 9:30-11:00 via Internet, Webex https://ibm.webex.com/meet/tomasz.stopa
W programie:
Marcin Wierzbiński - University of Warsaw, Faculty of Mathematics, Informatics and Mechanics, AstroCENT, Nicolaus Copernicus Astronomical Center, Polish Academy of Sciences
Temat: Mapping MAX-2-SAT to Ising model
PrezentacjaAbstract:
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. .
References:
[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}