An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables

In this paper, we propose a novel quantum learning algorithm, based on Younes' quantum circuit, to find dependent variables of the Boolean function $f:{\left\{0,1\right\}}^n\to \left\{0,1\right\}$ with one uncomplemented product of two variables. Typically, in the worst-case scenario, two dependent variables are found by evaluating the function $O\left(n\right)$ times. However, our proposed quantum algorithm only requires $O\left({\log }_{2}n\right)$ function operations in the worst-case. Additionally, we evaluate the average number to perform the function. In the average case, our algorithm requires $O\left(1\right)$ function operations.