We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let @math be a Boolean function and consider a function @math obtained by applying @math to conjunctions of possibly overlapping subsets of @math variables. If @math has quantum query complexity @math , we give an algorithm for evaluating @math using @math quantum queries. This improves on the bound of @math that follows by treating each conjunction independently, and is tight for worst-case choices of @math . Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of @math . By recursively applying our composition theorems, we obtain a nearly optimal @math upper bound on the quantum query complexity and approximate degree of linear-size depth- @math AC @math circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponential-time algorithm was not known even for linear-size depth-3 AC @math circuits. We also show that any substantially faster learning algorithm will require fundamentally new techniques.
Given the current state of affairs, a subexponential-time algorithm to learn all of in the standard PAC model would represent significant progress. Indeed, for @math , the fastest known PAC learning algorithm for depth- @math circuits runs in time @math @cite_10 , which is quite close to the trivial runtime of @math .
@cite_10
2773065828
Despite decades of intensive research, efficient - or even sub-exponential time - distribution-free PAC learning algorithms are not known for many important Boolean function classes. In this work we suggest a new perspective on these learning problems, inspired by a surge of recent research in complexity theory, in which the goal is to determine whether and how much of a savings over a naive 2^n runtime can be achieved. We establish a range of exploratory results towards this end. In more detail, (1) We first observe that a simple approach building on known uniform-distribution learning results gives non-trivial distribution-free learning algorithms for several well-studied classes including AC0, arbitrary functions of a few linear threshold functions (LTFs), and AC0 augmented with mod_p gates. (2) Next we present an approach, based on the method of random restrictions from circuit complexity, which can be used to obtain several distribution-free learning algorithms that do not appear to be achievable by approach (1) above. The results achieved in this way include learning algorithms with non-trivial savings for LTF-of-AC0 circuits and improved savings for learning parity-of-AC0 circuits. (3) Finally, our third contribution is a generic technique for converting lower bounds proved using Neciporuk's method to learning algorithms with non-trivial savings. This technique, which is the most involved of our three approaches, yields distribution-free learning algorithms for a range of classes where previously even non-trivial uniform-distribution learning algorithms were not known; these classes include full-basis formulas, branching programs, span programs, etc. up to some fixed polynomial size.