Issue Details
QUANTUM LEAP: A POLYNOMIAL-TIME ALGORITHM FOR DUALIZATION PROBLEMS
Ms. Jyoti
Page No. : 176-181
ABSTRACT
In the context of two prime monotone boolean functions, denoted as f : {0,1}n → {0,1} and g : {0,1}n → {0,1}, the Dualization Problem arises when we aim to determine whether g is the dual counterpart of f. In other words, we seek to establish if, for all possible inputs (x1,...,xn) belonging to {0, 1}n, the values of f(x1,...,xn) and g ̅((x1) ̅,...,(xn) ̅) are identical. This Dualization Problem can also be formulated as a decision problem: when presented with two monotone prime boolean functions, f and g, our objective is to determine if g indeed serves as the dual function to f.
This paper introduces a quantum computing algorithm specifically designed to address the decision variant of the Dualization Problem efficiently. Our algorithm exhibits a polynomial time complexity, offering a significant improvement over classical methods.
FULL TEXT
