Efficient Quantum Answer Set Programming Solver Using Partial Diffusion and Entanglement

Abstract

The relation between answer set programming (ASP) and combinatorial problems, especially the satisfiability problem (SAT), has attracted significant interest in the academic literature. This paper aims to introduce an efficient quantum answer set programming solver (QSAT) that can handle NP-hard combinatorial search problems by reducing the problem to MAX-3-SAT problem. This paper proposes a quantum algorithm that solves the MAX-3-SAT problem using amplification techniques that exploit entanglement and partial diffusion operator to find a solution with a high probability in <inline-formula> <tex-math notation="LaTeX">$O\left ({{ \sqrt {\frac {2^{n}}{l}} }}\right )$ </tex-math></inline-formula>, where n is the number of variables and l denotes the number of literals. The proposed algorithm shows a speed-up in solving ASP problems compared with classical approaches.