Efficient Quantum Answer Set Programming Solver Using Partial Diffusion and Entanglement
Open Access
- 11 November 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 13, 193201-193214
Abstract
The relation between answer set programming (ASP) and combinatorial problems, especially the satisfiability problem (SAT) has attracted significant interest in academic literature. The aim of this paper is 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. The paper proposes a quantum algorithm that solves the MAX-3-SAT problem using amplification techniques that exploits entanglement and partial diffusion operator to find a solution with high probability in O(√2n/l), 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 to classical approaches.Keywords
This publication has 55 references indexed in Scilit:
- A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Teleportation2024
- Qubits, Quantum Bits, and Quantum Computing2023
- Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization2023
- P, NP, NP-Complete, and NP-Hard Problems2022
- Answer Set Programming2019
- lp2normal — A Normalization Tool for Extended Logic Programs2017
- Inapproximability of Combinatorial Optimization Problems2013
- Conjunctive Normal Form2011
- Declarative Problem-Solving Using the DLV System2000
- Smodels — an implementation of the stable model and well-founded semantics for normal logic programsLecture Notes in Computer Science, 1997