Heuristics for Quantum Computing Dealing with 3-SAT

Jose J. Paulet (), Luis F. LLana, Hernán Indíbil Calvo, Mauro Mezzini, Fernando Cuartero and Fernando L. Pelayo ()
Additional contact information
Jose J. Paulet: Departamento de Sistemas Informaticos y Computacion, Facultad de Informatica, Complutense University, 28040 Madrid, Spain
Luis F. LLana: Departamento de Sistemas Informaticos y Computacion, Facultad de Informatica, Complutense University, 28040 Madrid, Spain
Hernán Indíbil Calvo: Departamento de Sistemas Informaticos, Escuela Superior de Ingenieria Informatica, University of Castilla—La Mancha, 02071 Albacete, Spain
Mauro Mezzini: Dipartimento di Scienze della Formazione, Via del Castro Pretorio 20, UniRoma3, 00185 Rome, Italy
Fernando Cuartero: Departamento de Sistemas Informaticos, Escuela Superior de Ingenieria Informatica, University of Castilla—La Mancha, 02071 Albacete, Spain
Fernando L. Pelayo: Departamento de Sistemas Informaticos, Escuela Superior de Ingenieria Informatica, University of Castilla—La Mancha, 02071 Albacete, Spain

Mathematics, 2023, vol. 11, issue 8, 1-24

Abstract: The SAT problem is maybe one of the most famous NP-complete problems. This paper deals with the 3-SAT problem. We follow a sort of incremental strategy to save computational costs with respect to the classical quantum computing approach. We present an heuristics that leads this strategy, improving the performance of the purely random incremental scheme. We finally validate our approach by means of a thorough empirical study.

Keywords: computational efficiency; DPLL algorithm; Grover algorithm; SAT problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/8/1888/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/8/1888/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:8:p:1888-:d:1124800

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().