  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).
