Sponsor
This article’s publication was funded by the Portland State University Open Access Article Processing Charge Fund, administered by the Portland State University Library.
Published In
Entropy
Document Type
Article
Publication Date
10-2022
Subjects
Quantum computers, Quantum theory, Quantum computers -- Testing
Abstract
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.
Rights
© 2022 by the authors. Licensee MDPI, Basel, Switzerland.
This article is an open access article distributed under the terms and conditions of the a Creative Commons Attribution 4.0 International License.
DOI
10.3390/e24111615
Persistent Identifier
https://archives.pdx.edu/ds/psu/38715
Citation Details
Alasow, A.; Jin, P.; Perkowski, M. Quantum Algorithm for Variant Maximum Satisfiability. Entropy 2022, 24, 1615. https://doi.org/10.3390/e24111615