Given two positive Boolean functions f: {0, 1}^n -> {0, 1} and g : {0, 1}^n -> {0, 1} expressed in their positive irredundant DNF Boolean formulas, the dualization problem consists in determining if g is the dual of f , that is if f (x1, . . . , xn) = g(x1, . . . xn) for all (x1, . . . xn) in {0, 1}^n. In this paper we present a quantum computing algorithm that solves the dualization problem in polynomial time with respect to the dimensions of the DNF expressions
Mezzini, M., Cuartero Gomez, F., Lopez Pelayo, F., Javier Paulet Gonzalez, J., Indibil de la Cruz Calvo, H., Pascual, V. (2023). A polynomial quantum computing algorithm for solving the dualization problem for positive boolean functions. In AI for Quantum and Quantum for AI 2023.
A polynomial quantum computing algorithm for solving the dualization problem for positive boolean functions
Mauro Mezzini
Investigation
;
2023-01-01
Abstract
Given two positive Boolean functions f: {0, 1}^n -> {0, 1} and g : {0, 1}^n -> {0, 1} expressed in their positive irredundant DNF Boolean formulas, the dualization problem consists in determining if g is the dual of f , that is if f (x1, . . . , xn) = g(x1, . . . xn) for all (x1, . . . xn) in {0, 1}^n. In this paper we present a quantum computing algorithm that solves the dualization problem in polynomial time with respect to the dimensions of the DNF expressionsI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
