Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Quantum Information Science

Quantum Algorithm for Solving Tautology and Satisfiability Problems

Amrita Mitra

Published Jan 1, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.4236/jqis.2026.161004

Related papers

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

A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability

Ahmed Younes, Jonathan E. Rowe

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.

arXiv:1507.05061•Jul 16, 2015•4 citations

Classical and Quantum Algorithms for the Boolean Satisfiability Problem

Carlos Barrón-Romero

This paper presents a complete algorithmic study of the decision Boolean Satisfiability Problem under the classical computation and quantum computation theories. The paper depicts deterministic and probabilistic algorithms, propositions of their properties and the main result is that the problem has not an efficient algorithm (NP is not P). Novel quantum algorithms and propositions depict that the complexity by quantum computation approach for solving the Boolean Satisfiability Problem or any NP problem is lineal time.

arXiv:1510.02682•Oct 6, 2015•3 citations

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

A linear time quantum algorithm for 3SAT

Zachary B. Walters

A quantum algorithm for the NP complete problem of satisfying boolean formulas with three variables per clause (3SAT) is presented. Departing from traditional models of quantum computation, this algorithm makes extensive use of irreversible operations to incoherently transfer population from states which do not solve some problem of interest to states which do. Provided that a solution exists, the algorithm yields exponential decay of nonsolution probability, at a rate controlled by the user.

•Sep 29, 2015•0 citations

Quantum Algorithm for Variant Maximum Satisfiability

Abdirahman Alasow, Peter Jin, Marek A. Perkowski

In this paper, we proposed a novel quantum algorithm for the maximum satisfiability problem. Satisfiability (SAT) is to find the set of assignment values of input variables for the given Boolean function that evaluates this function as TRUE or prove that such satisfying values do not exist. For a POS SAT problem, we proposed 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 information on how far the given Boolean function is from the SAT satisfaction. We used Grover’s algorithm with a new block called quantum counter in the oracle circuit. The proposed circuit can be adapted for various forms of satisfiability expressions and several satisfiability-like problems. Using the quantum counter and mirrors for SAT terms reduces the need for ancilla qubits and realizes a large Toffoli gate that is then not needed. Our circuit reduces the number of ancilla qubits for the terms T of the Boolean function from T of ancilla qubits to ≈log2T+1. We analyzed and compared the quantum cost of the traditional oracle design with our design which gives a low quantum cost.

Entropy•Nov 5, 2022•3 citations
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.
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 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(m2)O(m^2)O(m2) for an E3-CNF Boolean formula with mmm clauses and in the worst case runs in O(n6)O(n^6)O(n6) for an E3-CNF Boolean formula with nnn 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−ε1-ε1−ε for small ε>0ε>0ε>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.
This paper presents a complete algorithmic study of the decision Boolean Satisfiability Problem under the classical computation and quantum computation theories. The paper depicts deterministic and probabilistic algorithms, propositions of their properties and the main result is that the problem has not an efficient algorithm (NP is not P). Novel quantum algorithms and propositions depict that the complexity by quantum computation approach for solving the Boolean Satisfiability Problem or any NP problem is lineal time.
In this paper, we proposed a novel quantum algorithm for the maximum satisfiability problem. Satisfiability (SAT) is to find the set of assignment values of input variables for the given Boolean function that evaluates this function as TRUE or prove that such satisfying values do not exist. For a POS SAT problem, we proposed 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 information on how far the given Boolean function is from the SAT satisfaction. We used Grover’s algorithm with a new block called quantum counter in the oracle circuit. The proposed circuit can be adapted for various forms of satisfiability expressions and several satisfiability-like problems. Using the quantum counter and mirrors for SAT terms reduces the need for ancilla qubits and realizes a large Toffoli gate that is then not needed. Our circuit reduces the number of ancilla qubits for the terms T of the Boolean function from T of ancilla qubits to ≈log2T+1. We analyzed and compared the quantum cost of the traditional oracle design with our design which gives a low quantum cost.