© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1507.05061

A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability

Ahmed Younes, Jonathan E. Rowe

Published Jul 16, 2015• 4 citations

Abstract

The aim of the paper is to answer a long-standing open problem on the relationship between NP and BQP. The paper shows that BQP contains NP by proposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a fundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the MAX-E3-SAT problem is to find the variable assignment that maximizes the number of satisfied clauses. The proposed algorithm runs in $O(m^2)$ for an E3-CNF Boolean formula with $m$ clauses and in the worst case runs in $O(n^6)$ for an E3-CNF Boolean formula with $n$ inputs. The proposed algorithm maximizes the set of satisfied clauses using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of $1-ε$ for small $ε>0$ using a polynomial resources. In addition to solving the MAX-E3-SAT problem, the proposed algorithm can also be used to decide if an E3-CNF Boolean formula is satisfiable or not, which is an NP-complete problem, based on the maximum number of satisfied clauses.

DOI: 10.48550/arxiv.1507.05061

Related papers

A quantum method to test the satisfiability of Boolean functions

Jin Qiang Wang, Jialin Chen, Chaofan Yu +1 more

Satisfiability (SAT) problem is one of the NP-hard problems. General SAT problem can be solved in polynomial time when the given formula contains only binary clauses (2-SAT). Quantum computation possesses some virtues that exceeding classical computation in speed, therefore it has the potential ability to solve NP-complete problems better than with classical methods. This paper introduces a new method to test the satisfiability of Boolean functions based on quantum ETOF gates.

IEEE International Conference on Solid-State and Integrated Circuit Technology•Oct 1, 2012•0 citations

Quantum Answer Set Programming Solver Using Amplitude Amplification

Esraa Ebdelrehime, Ahmed Younes, Islam Elkabani

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.

International Conference on Machine Intelligence and Smart Innovation (ICMISI)•May 12, 2024•1 citation

Quantum Algorithm for Solving Tautology and Satisfiability Problems

Amrita Mitra

This paper proposes a quantum algorithm for solving the tautology and the satisfiability problems for a Boolean formula. Let’s say we are given a Boolean formula. The variables of the Boolean formula can take only two values—TRUE or FALSE. The tautology problem asks whether the Boolean formula always evaluates to TRUE for all values of its Boolean variables. The satisfiability problem asks whether the Boolean formula can evaluate to TRUE for at least one set of values of its Boolean variables. This paper proposes that both problems can be solved using the proposed quantum algorithm. The tautology problem is known to be co-NP-complete. The satisfiability problem is known to be NP-complete.

Journal of Quantum Information Science•Jan 1, 2026•0 citations

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Θ(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $Θ(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $Ω(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $Ω(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943•Leibniz international proceedings in informatics•Jan 1, 2024•0 citations

Quantum Algorithm for Maximum Satisfiability

Abdirahman Alasow, Marek A. Perkowski

Satisfiability (SAT) problem in engineering and computer science is to find the set of assignment values of input variables for the given Boolean function that evaluate this function to TRUE or prove that such satisfying values do not exist. For POS SAT Problem, we propose a novel quantum algorithm for the maximum satisfiability (MAX-SAT) which returns the maximum number of OR terms that are satisfied for the SAT-unsatisfiable function, providing us with the information how far the given Boolean function is from the SAT satisfaction. We use Grover's algorithm with a new block called quantum counter in the oracle circuit.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2022•7 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 Access•Jan 1, 2025•0 citations

The aim of the paper is to answer a long-standing open problem on the relationship between NP and BQP. The paper shows that BQP contains NP by proposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a fundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the MAX-E3-SAT problem is to find the variable assignment that maximizes the number of satisfied clauses. The proposed algorithm runs in

O(m^2)

for an E3-CNF Boolean formula with

m

clauses and in the worst case runs in

O(n^6)

for an E3-CNF Boolean formula with

n

inputs. The proposed algorithm maximizes the set of satisfied clauses using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of

1-ε

for small

ε>0

using a polynomial resources. In addition to solving the MAX-E3-SAT problem, the proposed algorithm can also be used to decide if an E3-CNF Boolean formula is satisfiable or not, which is an NP-complete problem, based on the maximum number of satisfied clauses.

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.

This paper proposes a quantum algorithm for solving the tautology and the satisfiability problems for a Boolean formula. Let’s say we are given a Boolean formula. The variables of the Boolean formula can take only two values—TRUE or FALSE. The tautology problem asks whether the Boolean formula always evaluates to TRUE for all values of its Boolean variables. The satisfiability problem asks whether the Boolean formula can evaluate to TRUE for at least one set of values of its Boolean variables. This paper proposes that both problems can be solved using the proposed quantum algorithm. The tautology problem is known to be co-NP-complete. The satisfiability problem is known to be NP-complete.

What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires

Θ(n)

queries to an NP oracle to compute a witness to a given SAT formula, quantumly

Θ(\log n)

queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires

Ω(\log n)

queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires

Ω(\log n)

queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making

o(log n)

NP queries, then

\text{BPP}^{\text{NP}[o(n)]}

contains a

\text{P}^{\text{NP}}

-complete problem if the algorithm is classical and

\text{FBQP}^{\text{NP}[o(n)]}

contains an

\text{FP}^{\text{NP}}

-complete problem if the algorithm is quantum.

Satisfiability (SAT) problem in engineering and computer science is to find the set of assignment values of input variables for the given Boolean function that evaluate this function to TRUE or prove that such satisfying values do not exist. For POS SAT Problem, we propose a novel quantum algorithm for the maximum satisfiability (MAX-SAT) which returns the maximum number of OR terms that are satisfied for the SAT-unsatisfiable function, providing us with the information how far the given Boolean function is from the SAT satisfaction. We use Grover's algorithm with a new block called quantum counter in the oracle circuit.

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.