Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions

Abstract In this paper, we present quantum computing algorithms for solving the dualization problem in polynomial time with respect to the asymptotic dimensions of the positive irredundant Disjunctive Normal Form. Furthermore, we give a quantum annealing algorithm for solving the dualization problem using a quantum annealer. Moreover, we reduce the dualization problem to the problem of counting all the hitting sets of a hypergraph