Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1311.6777 · Computational Complexity

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound

Aleksandrs Belovs

Published Apr 16, 2015• 39 citations
arXivHTMLPDF
DOI
10.1007/s00037-015-0099-2

Related papers

Quantum Algorithms for Learning and Testing Juntas

Alp Atıcı, Rocco A. Servedio

arXiv:0707.3479•Quantum Information Processing•Sep 2, 2007•93 citations

A Exact Quantum Learning Algorithm for the 2-Junta Problem in Constant Time

Chien-Yuan Chen

International Journal of Theoretical Physics•Aug 3, 2022•4 citations

An Exact Quantum Algorithm for the 2-Junta Problem

Chien-Yuan Chen

International Journal of Theoretical Physics•Jan 1, 2021•5 citations

Quantum Algorithm for Distribution-Free Junta Testing

Aleksandrs Belovs

Lecture notes in computer science•Jan 1, 2019•12 citations

Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound

Aleksandrs Belovs

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. This is a generalisation of the Bernstein-Vazirani problem [1] (when h is the XOR function) and the combinatorial group testing problem [2] (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is square root of k) or the exact-half function (complexity is the fourth power root of k). The first algorithm resolves an open problem from. For the case when h is the majority function, we prove an upper bound of the fourth power root of k. 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 when compared to the non-adaptive quantum complexity (for all functions considered in the paper).

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2014•7 citations

Adversary lower bounds for nonadaptive quantum algorithms

Pascal Koiran, Jürgen Landes, Natacha Portier +1 more

arXiv:0804.1440•Journal of Computer and System Sciences•Oct 17, 2009•8 citations
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. This is a generalisation of the Bernstein-Vazirani problem [1] (when h is the XOR function) and the combinatorial group testing problem [2] (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is square root of k) or the exact-half function (complexity is the fourth power root of k). The first algorithm resolves an open problem from. For the case when h is the majority function, we prove an upper bound of the fourth power root of k. 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 when compared to the non-adaptive quantum complexity (for all functions considered in the paper).