A polynomial quantum computing algorithm for solving the dualization problem

Abstract

Given two prime monotone boolean functions $f:\{0,1{\}}^n\to \{0,1\}$ and $g:\{0,1{\}}^n\to \{0,1\}$ the dualization problem consists in determining if $g$ is the dual of $f$, that is if $f(x_1,\dots ,x_n)=\overline{g}(\overline{x_1},\dots \overline{x_n})$ for all $(x_1,\dots x_n)\in \{0,1{\}}^n$. Associated to the dualization problem there is the corresponding decision problem: given two monotone prime boolean functions $f$ and $g$ is $g$ the dual of $f$? In this paper we present a quantum computing algorithm that solves the decision version of the dualization problem in polynomial time.