Speeding up Answer Set Programming by Quantum Computing

Quantum Computing has become a more and more prominent research field in the last few decades. This growth in interest is mainly related to the so-called quantum speed up that some quantum procedure exhibits. The two main examples are Shor and Grover algorithms. The latter will be a key ingredient of this paper. In particular, we propose an attempt to speed up Answer Set Programming (ASP) exploiting Quantum Computing. We rely on two proposals in the literature that use quantum computation for: finding stable models of ASP programs; counting solutions of propositional formulae. For combining such proposals we embed in the quantum framework a third proposal from the literature, namely a purely classical approach for navigating the solution space of ASP models. We end up with a quantum method for counting stable models of ASP programs. After providing the details of our method, we briefly describe a Proof of Concept implementation of these techniques.