An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product (Q2118738)

The author suggests exact quantum algorithms for solving a particular example of the \(k\)-junta problem. The proposed algorithm can be used to find dependent variables of a Boolean function \(f(x_0,\ldots,x_{n-1}) = x_{g_1}\cdots x_{g_k}\). After an introduction to related results, the paper uses a modification of methods developed in earlier works [\textit{C.-Y. Chen}, Quantum Inf. Process. 19, No. 7, Paper No. 213, 12 p. (2020; Zbl 07649751); Quantum Inf. Process. 20, No. 1, Paper No. 36, 22 p. (2021; Zbl 07654151)] for two and three dependent variables, respectively, to \(k \ge 4\). An analysis of the suggested algorithms both in the worst-case and in the average-case is finally provided.