arXiv:2609.30139
A General Composition Theorem for Approximate Degree
Samruddhi Pednekar, Supartha Podder
Abstract
A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.
AI Summary
Approximate degree is a standard lower-bound measure for quantum query complexity, but its behavior under block composition was previously understood only in restricted cases. This paper proves that for all total Boolean functions $f$ and $g$, $\widetilde{\deg}(f\circ g)=\Omega(\widetilde{\deg}(f)\widetilde{\deg}(g))$. Combined with the known multiplicative upper bound, this gives a constant-factor composition theorem, without polylogarithmic losses. The proof averages an approximating polynomial for $f\circ g$ over parameterized input distributions. A dual witness for $g$ defines a degree-filtered operator whose unitary evolution produces probability distributions with derivative scale $\Theta(\widetilde{\deg}(g))$. Averaging preserves boundedness and converts polynomial degree into a bound on total trigonometric frequency. Squarefree extraction recovers an approximation to $f$; bounds on homogeneous Taylor components show that insufficient degree would permit truncation below $\widetilde{\deg}(f)$, yielding a contradiction. Warm-up results treat inner OR and adjacent-layer promise thresholds. The general theorem concerns total functions; the promise-threshold extension uses bounded approximate degree rather than unrestricted approximation on the promise. The paper also shows that exact quantum query complexity lacks an analogous multiplicative lower bound. It constructs an exact algorithm satisfying $Q_E(f\circ\mathrm{OR}_m)=O(m\deg(f)+n^2\sqrt m)$ by coherently correcting bounded-error computations. For explicit recursively composed functions on $4^k$ bits and $m_k=64^k$, the composed complexity is $O(128^k)$, whereas the product of the individual exact complexities is $\Omega(160^k)$. Their ratio is therefore $O((4/5)^k)$ and tends to zero.
We used ChatGPT (GPT-6 Astra) to assist with exploring research directions, identifying potential errors in arguments, simplifying proof strategies, and improving the exposition.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- Added a counterexample to multiplicative composition for exact quantum query complexity