Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
arXiv:1311.6777
Abstract
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function on variables that only depends on variables, and, when restricted to them, equals some predefined function . The task is to identify the variables the function depends on. When is the XOR or the OR function, this gives a restricted variant of the Bernstein-Vazirani or the combinatorial group testing problem, respectively. 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 is the OR function (complexity is ) or the exact-half function (complexity is ). The first algorithm resolves an open problem from arXiv:1210.1148. For the case when is the majority function, we prove an upper bound of . All these algorithms can be made exact. We obtain a quartic improvement when compared to the randomised complexity (if 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).
arXiv comment19 pages, many parts re-written, some references and minor results added
References in corpus (16)
- Quantum Amplitude Amplification and Estimation
- Exponential algorithmic speedup by quantum walk
- Grover's quantum searching algorithm is optimal
- Negative weights make adversaries stronger
- The quantum query complexity of the hidden subgroup problem is polynomial
- Quantum query complexity of state conversion
- Improved Bounds on Quantum Learning Algorithms
- Span-program-based quantum algorithm for evaluating formulas
- Learning-Graph-Based Quantum Algorithm for k-distinctness
- Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem
- Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
- Quantum Counterfeit Coin Problems
- An optimal quantum algorithm for the oracle identification problem
- Quantum lower bounds by quantum arguments
- Easy and hard functions for the Boolean hidden shift problem
- All Quantum Adversary Methods are Equivalent