Quantum algorithms and approximating polynomials for composed functions with shared inputs

Quantum 5, 543 (2021).

https://doi.org/10.22331/q-2021-09-16-543

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 $tilde{O}(sqrt{Q(f) cdot n})$ quantum queries. This improves on the bound of $O(Q(f) cdot sqrt{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 $tilde{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.
As an additional consequence, we show that AC$^0 circ oplus$ circuits of depth $d+1$ require size $tilde{Omega}(n^{1/(1- 2^{-d})}) geq 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).