Heuristics for Quantum Computing Dealing with 3-SAT

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