Published In
Journal of Applied Logics
Document Type
Article
Publication Date
12-2023
Subjects
Data Mining
Abstract
Covering problems find applications in many areas of computer science and engineering, such that numerous combinatorial problems can be formulated as covering problems. Combinatorial optimization problems are generally NPhard problems that require an extensive search to find the optimal solution. Exploiting the benefits of quantum computing, we present a quantum oracle design for covering problems, taking advantage of Grover’s search algorithm to achieve quadratic speedup. This paper also discusses applications of the quantum counter in unate covering problems and binate covering problems with some important practical applications, such as finding prime implicants of a Boolean function, implication graphs, and minimization of incompletely specified Finite State Machines.
Rights
Copyright (c) 2023 The Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
Persistent Identifier
https://archives.pdx.edu/ds/psu/41023
Citation Details
Alasow, Abdirahman and Perkowski, Marek, "Quantum Algorithms for Unate and Binate Covering Problems with Application to Finite State Machine Minimization" (2023). Electrical and Computer Engineering Faculty Publications and Presentations. 768.
https://archives.pdx.edu/ds/psu/41023
Corrigendum
Grover_s_Ternary_Diffusion_Operator - Marek Perkowski.pdf (827 kB)
Errata
Description
See additional file below for Corrigendum published in Vol. 11 No. 2 2024 Journal of Applied Logics—IfCoLog Journal of Logics and their Applications.
We, the authors of the paper entitled “Quantum algorithms for unate and binate covering problems with application to finite state machine minimization” published in Journal of Applied Logics in 2023, would like to clarify that Figure 13 in our paper use a variant of Grover diffusion circuit that is not a standard Grover diffusion operator for the Boolean oracles and the phase oracles of L.K. Grover as presented in [Grover 1996]. However, this variant of Grover diffusion circuit in this figure is the same as the quantum diffuser proposed by [ALI below], which is the so-called “Grover controlled-diffusion operator”. For this reason, we would like to publish this clarification as “Corrigendum” in the Journal of Applied Logics. [ALI] A. A-Bayaty and M. Perkowski, “A concept of controlling Grover diffusion operator: A new approach to solve arbitrary Boolean-based problems,” submitted to Scientific Reports, 2023. Nature.