Varotti, Stefano (2019) Effectively Encoding SAT and Other Intractable Problems into Ising Models for Quantum Computing. PhD thesis, University of Trento.
|PDF - Disclaimer |
Restricted to Repository staff only until 9999.
|PDF - Doctoral Thesis|
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.
|Item Type:||Doctoral Thesis (PhD)|
|Doctoral School:||Information and Communication Technology|
|Subjects:||Area 01 - Scienze matematiche e informatiche > INF/01 INFORMATICA|
|Repository Staff approval on:||27 May 2019 09:38|
Repository Staff Only: item control page