Quantum Algorithm for Solving Tautology and Satisfiability Problems

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.