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 an m-bit Boolean function and consider an n-bit 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) over tilde(root Q(f).n) quantum queries. This improves on the bound of O(Q(f).root n) that follows by treating each conjunction independently, and our bound 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) over tilde (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. As an additional consequence, we show that AC(0) circle circle plus circuits of depth d +1 require size (Omega) over tilde (n(1/(1-2-d))) > omega(n(1+2-d)) to compute the Inner Product function even on average. The previous best size lower bound was Omega(n(1+4-(d+1))) and only held in the worst case (Cheraghchi et al., JCSS 2018).

Automated summary

New quantum algorithms have been proposed for evaluating composed functions, and tight composition theorems for linear-size depth-d AC(0) circuits have been proven. Additionally, it has been shown that AC(0) circuits of depth d+1 require a larger size to compute the Inner Product function, even on average.