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.
Mezzini, M., Cuartero Gomez, F., Gonzalez, J.J.P., de la Cruz Calvo, H.I., Pascual, V., L. Pelayo, F. (2024). Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions. QUANTUM MACHINE INTELLIGENCE, 6(2) [10.1007/s42484-024-00202-y].
Polynomial quantum computing algorithms for solving the dualization problem for positive Boolean functions
Mezzini, Mauro
Investigation
;
2024-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
