English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

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 onlydepends on $k$ variables, and, when restricted to them, equals some predefinedfunction $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 theBernstein-Vazirani or the combinatorial group testing problem, respectively.  We analyse the general case using the adversary bound, and give analternative formulation for the quantum query complexity of this problem. Weconstruct optimal quantum query algorithms for the cases when $h$ is the ORfunction (complexity is $\Theta(\sqrt{k})$) or the exact-half function(complexity is $\Theta(k^{1/4})$). The first algorithm resolves an open problemfrom arXiv:1210.1148. For the case when $h$ is the majority function, we provean upper bound of $O(k^{1/4})$. All these algorithms can be made exact.  We obtain a quartic improvement when compared to the randomised complexity(if $h$ is the exact-half or the majority function), and a quadratic one whencompared to the non-adaptive quantum complexity (for all functions consideredin the paper).

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound