Università degli studi di Trento
Effectively Encoding SAT and Other Intractable Problems into Ising Models for Quantum Computing
Abstract
dc:descriptionQuantum 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.
Degree
thesis:*- Grantor dc:publisher
- Università degli studi di Trento
- Year dc:date
- 2019
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Varotti, Stefano
- Contributors dc:contributor
-
- Sebastiani, Roberto
Subjects
dc:subject × 1Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- license:Tutti i diritti riservati (All rights reserved)
- license uri:iris.PRI01
- Language dc:language
- eng
Identifiers
dc:identifier.*- OAI identifier oai:identifier
- oai:iris.unitn.it:11572/368161