Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound

摘要

In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on.When h is the XOR or the OR function, this gives a restricted variant of the Bernstein-Vazirani or the combinatorial group testing problem, respectively.