Quantum algorithms and approximating polynomials for composed functions with shared inputs

摘要

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let f be a Boolean function and consider a function F obtained by applying f to conjunctions of possibly overlapping subsets of n variables. If f has quantum query complexity Q ( f ) , we give an algorithm for evaluating F using O ( Q ( f ) n ) quantum queries. This improves on the bound of O ( Q ( f ) n ) that follows by treating each conjunction independently, and is tight for worst-case choices of f . Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of f .By recursively applying our composition theorems, we obtain a nearly optimal O ( n 1 ? 2 ? d ) upper bound on the quantum query complexity and approximate degree of linear-size depth- d AC 0 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 0 circuits. We also show that any substantially faster learning algorithm will require fundamentally new techniques.