Quantum Answer Set Programming Solver Using Amplitude Amplification
Esraa Ebdelrehime, Ahmed Younes, Islam Elkabani · 2024
In this paper, a Quantum Answer set programming solver (QASP) will be proposed to solve NP-hard combinatorial search problems. The paper shows that problems such as Hamiltonian cycle problem and N-queen problem encoded as ASP can be reduced to a MAX-3-SAT problem in a 3-CNF form. The 3-CNF Boolean formula will be solved using the proposed quantum solver with$O(n+ m)$qubits where$n$is the input variables number,$m$is the clauses number in$O(\sqrt{2^{n/m}})$steps.