Department of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
Objectives:
• 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 https://ibm.webex.com/meet/tomasz.stopa
Program:
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
PresentationAbstract:
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}