An Exact Quantum Algorithm for the 2-Junta Problem

This paper proposes a novel quantum learning algorithm based on Bernstein and Vazirani’s quantum circuit to find the dependent variables of the 2-junta problem. Typically, for a given Boolean function f : {0, 1}n → {0, 1} that depends on only 2 out of n variables, the dependent variables are obtained by evaluating the function 4n times in the worst-case. However, the proposed quantum algorithm only requires O(log2n) function operations in the worst-case. Moreover, the algorithm requires an average of 5.3 function operations at the most when n ≥ 8.