Speeding up Answer Set Programming by Quantum Computing

Riccardo Romanello, Davide Della Giustina, Stefano Pessotto, Carla Piazza

Published Jun 3, 2024• 1 citation

Abstract

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.

DOI: 10.1145/3660318.3660328

Related papers

Finding stable models via quantum computation.

DAVID A. MEYER, James Pommersheim, Jeffrey B. Remmel

Quantum computers have the potential to out-perform classical computers—certain quantum algorithms run much faster than any known alternative classical algorithm. For example, Grover showed that a quantum computer can search an unordered list of N items in time O ( √ N), providing a quadratic speed-up over the classical algorithm. In this paper, we show that we can modify Grover’s search algorithm to give an algorithm that finds stable models of an Answer Set Program with a similar quadratic improvement over the classical algorithm. Marek and Remmel showed that Answer Set Programming (ASP) programs can uniformly solve all NP-search problems, so our quantum algorithm to find stable models of ASP programs also solves all NP-search problems. It follows that Answer Set Programming could provide a programming language for quantum computation.

Non-Monotonic ReasoningJan 1, 20042 citations

Efficient Quantum Answer Set Programming Solver Using Partial Diffusion and Entanglement

Esraa Ebdelrehime, Ahmed Younes, Islam Elkabani

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 inO(√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.

IEEE AccessJan 1, 20250 citations

Reflections on quantum computing

Cristian S. Calude, Michael J. Dinneen, Karl Svozil

In this rather speculative note three problems pertaining to the power and limits of quantum computing are posed and partially answered: a) when are quantum speedups possible?, b) is fixed-point computing a better model for quantum computing?, c) can quantum computing trespass the Turing barrier? 1 When are quantum speedups possible? This section discusses the possibility that speedups in quantum computing can be achieved only for problems which have a few or even unique solutions [12]. For instance, this includes the computational complexity class UP [15]. Typical examples are Shor's quantum algorithm for prime factoring [18] and Grover's database search algorithm [13] for a single item satisfying a given condition in an unsorted database (see also Gruska [14]). In quantum complexity, one popular class of problems is BQP,whichisthe set of decision problems that can be solved in polynomial time (on a quantum computer) so that the correct answer is obtained with probability at l...

ComplexitySep 1, 200025 citations

Quantum Algorithms: Overviews, Foundations, and Speedups

Shuangbao Paul Wang, Eric Sakk

This paper discusses quantum computing with a strong focus on quantum software, quantum networks, quantum simulation, and applications. The study on quantum speedups reveals fundamental differences between quantum algorithms and classical algorithms. As a case study, further improvement on Shor's algorithm is presented with experimental results. The study shows that quantum circuits can be generated automatically to further improve the efficiency of quantum algorithms.

International Conference on Cryptography, Security and Privacy (CSP)Jan 8, 202112 citations

Synthesis of CNOT minimal quantum circuits with topological constraints through ASP

Piazza C., Romanello R.

Although with some yet severe limitations, Physical working Quantum Computers are becoming available for end users. Such devices are based on the rules of Quantum Mechanics, which state that physical systems evolve through unitary transformations. However, as in the classical case, in order to have a model of computation, such unitary evolutions are expressed/approximated inside Quantum Computers in terms of a finite set of one/two qubit operations (i.e., through a universal set of gates). Single qubit gates are fault-tolerant, while the same cannot be said for two qubit gates. Hence, unitary matrices adopted in Quantum Algorithms must be synthesized in terms of this universal set of operations to obtain a quantum circuit. In such synthesis procedure we prefer circuits with minimum number of qubits and with minimum circuit depth. Clifford+T universal set is one of the most adopted in the literature for synthesis. In such set we have 3 single qubit gates and the CNOT, which is a two qubit gate. Many efforts have been directed to devise algorithms that synthesize general unitary matrices into Clifford+T circuits. These algorithms usually tend to optimize circuit depth or eventually the number of T gates. Since two qubit gates are not fault tolerant, in this work we propose an ASP based technique to minimize the number of CNOT gates inside a Clifford+T circuit. Moreover, in real world quantum computers, qubit are usually connected to each other according to some particular topology, thus providing further constraints. Two qubit gates —hence, CNOT gate— can be directly applied only to pair of gates that are connected. Such constraint has to be taken into account during the synthesis of CNOT minimal circuits. We propose an ASP model to solve the problem of synthesizing CNOT minimal circuits under topological constraints. We provide experimental evidence of the scalability of our proposal.

Jan 1, 20230 citations

An Efficient Framework to Utilize Grover Search

Shigeru, Yamashita, Masaki Masaki +1 more

This paper proposes an efficient framework to utilize quantum search practically.To the best of our knowledge,this is the first paper to show a concrete usage of quantum search in general programming.In our framework,we can utilize a quantum computer as a coprocessor to speed-up some parts of a program that runs on a classical computer.To do so,we propose several new ideas and techniques,such as a practical method to design a large quantum circuits for search problems and an efficient quantum comparator.

Jan 1, 20110 citations