Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions
摘要
In this paper, we present classical computing and 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 QUBO formulation of the dualization problem that can then be solved on a quantum annealer. Moreover, we reduce the dualization problem to the problem of counting all the hitting sets of a hypergraph.