2026-09-19T11:14:40Zhttps://iris.unitn.it/oai/requestoai:iris.unitn.it:11572/3681612026-04-03T00:48:26Zcom_11572_237821com_11572_101871col_11572_237822ou_ou00002
Effectively Encoding SAT and Other Intractable Problems into Ising Models for Quantum Computing
Varotti, Stefano
Varotti, Stefano
Sebastiani, Roberto
Settore INF/01 - Informatica
Quantum computing theory posits that a computer exploiting quantum mechanics can be strictly more powerful than classical models. Several quantum computing devices are under development, but current technology is limited by noise sensitivity. Quantum Annealing is an alternative approach that uses a noisy quantum system to solve a particular optimization problem. Problems such as SAT and MaxSAT need to be encoded to make use of quantum annealers. Encoding SAT and MaxSAT problems while respecting the constraints and limitations of current hardware is a difficult task. This thesis presents an approach to encoding SAT and MaxSAT problems that is able to encode bigger and more interesting problems for quantum annealing. A software implementation and preliminary evaluation of the method are described.
2019
info:eu-repo/semantics/doctoralThesis
https://hdl.handle.net/11572/368161
http://dx.doi.org/10.15168/11572_368161
10.15168/11572_368161
eng
firstpage:1
lastpage:151
numberofpages:151
info:eu-repo/semantics/openAccess
Università degli studi di Trento
place:TRENTO
license:Tutti i diritti riservati (All rights reserved)
license:Tutti i diritti riservati (All rights reserved)
license uri:iris.PRI01