LAUSR

This paper modifies Chen’s algorithm, which is the first exact quantum algorithm for testing 2-junta, and proposes an exact quantum learning algorithm for finding dependent variables of the Boolean function $$ f: \left\{ {0, 1} \right\}^{n} \to \left\{ {0, 1} \right\} $$ f : 0 , 1 n → 0 , 1 with one uncomplemented product of three variables. Typically, the dependent variables are obtained by evaluating the function $$ 2n $$ 2 n times in the worst case. However, our proposed quantum algorithm only requires $$ O\left( {\log_{2} n} \right) $$ O log 2 n function operations in the worst case. In addition, the average number to perform the function is evaluated. Our algorithm requires an average of $$ 7.23 $$ 7.23 function operations at the most when $$ n \ge 16 $$ n ≥ 16 . We also show that our algorithm cannot solve $$ k $$ k -junta problem with one uncomplemented product if $$ 4 \le k < n/2 $$ 4 ≤ k < n / 2 .