Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.30139

A General Composition Theorem for Approximate Degree

Samruddhi Pednekar, Supartha Podder

cs.CCquant-phSubmitted Sep 24, 2026• Announced Sep 25, 2026• 1 citation• Revised Oct 23, 2026 (v2)
v1 · Sep 24, 2026v2 · Oct 23, 2026
arXivHTMLPDF

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.

No sign of AI-generated textAI use disclosed
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

Related papers

A General Composition Theorem for Approximate Degree — E8 Intelligence Research

Andrew Stewart Caldin

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. Source: http://arxiv.org/abs/2609.30139v1 (arXiv:2609.30139v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 13, 2026•0 citations

On the Composition of Randomized Query Complexity and Approximate Degree

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal +3 more

For any Boolean functions f and g, the question whether $$\text {R}(f\circ g) = \tilde{\Theta }(\text {R}(f) \cdot \text {R}(g))$$ is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $$\widetilde{\text {deg}}(f\circ g) = \tilde{\Theta }(\widetilde{\text {deg}}(f)\cdot \widetilde{\text {deg}}(g))$$ . These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which $$\text {R}$$ and $$\widetilde{\text {deg}}$$ compose. A recent landmark result (Ben-David and Blais, 2020) showed that $$\text {R}(f \circ g) = \Omega (\text {noisyR}(f)\cdot \text {R}(g))$$ . This implies that composition holds iff $$\text {noisyR}(f) = \tilde{\Theta }(\text {R}(f))$$ . We show two results: On the other hand, we prove that $$ \widetilde{\text {deg}}(f\circ g) = \widetilde{\Omega }(\sqrt{\text {bs}(f)} \cdot \widetilde{\text {deg}}(g)), $$ where $$\text {bs}(f)$$ is the block sensitivity of f. This implies that $$\widetilde{\text {deg}}$$ composes when $$\widetilde{\text {deg}}(f)$$ is asymptotically equal to $$\sqrt{\text {bs}(f)}$$ . It is already known that both $$\text {R}$$ and $$\widetilde{\text {deg}}$$ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.

arXiv:2307.03900•Computational Complexity•Aug 20, 2026•10 citations

Composition Theorem for Randomized Query Complexity

Samruddhi Pednekar, Supartha Podder

For bounded-error randomized query complexity, we resolve the composition conjecture up to logarithmic factors. The general upper bound $R(f\circ g) = O\!\left(R(f)R(g)\log(R(f)+1)\right)$ was already known. Although Meiburg recently disproved constant-factor multiplicative composition for total Boolean functions, the conjecture allowing polylogarithmic losses remained open. We settle this question by proving that, for all (possibly partial) Boolean functions $f$ and $g$, \[ R(f\circ g) = Ω\!\left(\frac{R(f)R(g)}{\log(n+1)}\right), \] where $n$ is the input size for $f$.

arXiv:2611.08574•Nov 5, 2026•0 citations

Lower Bounds for the Approximate Degree of Block-Composed Functions

Justin Thaler

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function f on N bits, define F(x_1,...,x_M) = OMB(f(x_1),...,f(x_M)) to be the function on M*N bits obtained by block-composing f with a function known as ODD-MAX-BIT. We show that, if f requires large degree to approximate to error 2/3 in a certain one-sided sense (captured by a complexity measure known as positive one-sided approximate degree), then F requires large degree to approximate even to error 1-2^{-M}. This generalizes a result of Beigel (Computational Complexity, 1994), who proved an identical result for the special case f=OR. Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions F that have low threshold degree. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function. We describe several applications, including improved separations between the complexity classes P^{NP} and PP in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).

Leibniz international proceedings in informatics•Jan 1, 2016•21 citations

Approximate Degree Composition for Recursive Functions

Sourav Chakraborty, Chandrima Kayal, Mittal, Rajat +2 more

Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e.~functions obtained by composing a base function with itself a number of times. Let $h^d$ denote the standard $d$-fold composition of the base function $h$. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: (I) The outer function $f:\{0,1\}^n\to \{0,1\}$ is a recursive function of the form $h^d$, with $h$ being any base function and $d= Ω(\log\log n)$. (II) The inner function is a recursive function of the form $h^d$, with $h$ being any constant arity base function (other than AND and OR) and $d= Ω(\log\log n)$, where $n$ is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be \emph{efficiently eliminated} if the inner or outer function is a recursive function.

arXiv:2407.08385•Leibniz international proceedings in informatics•Jan 1, 2024•3 citations

Exact Quantum Algorithms for Composed Boolean Functions

Gagan Chiruvella, Chandrima Kayal, Rajat Mittal +2 more

We study exact quantum algorithms for block compositions of total Boolean functions. For an outer function $f$ of degree $D$ and an inner function $g$ on $m$ bits, we prove $$ Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right). $$ The algorithm combines approximate inner evaluations with a finite exact correction. Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction. We first establish the construction with an arity-dependent error threshold and then obtain the degree-dependent threshold above. For recursive ternary not-all-equal, this gives an exact algorithm using $(3/\sqrt2)^{k(1+o(1))}$ queries asymptotically. More generally, for every fixed nonconstant total gadget $h$, we determine the exact recursive rate as $\max\{\textrm{deg}(h),\operatorname{Adv}^{\pm}(h)\}$ and prove $Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2)$. The composition limit also allows to transfer separations from $Q_{\varepsilon}$ and $°$ to exact quantum query complexity $Q_E$ (similar to fractional block sensitivity to block sensitivity transfer in Tal and Kulkarni 2016, Chicago Journal of Theoretical Computer Science). We construct a family with $s=\operatorname{bs}=\operatorname{fbs}\ge Q_E^{3/2-o(1)}$, improving the previous exponent $1.1527\ldots$. A second construction gives $R \ge Q_E^{2-o(1)}$, improving the previous exponent $3/2$. We also allow different inner functions and give analogous quantitative separations in quantum communication.

arXiv:2611.16412•Nov 12, 2026•0 citations
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→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} and g:{0,1}m→{0,1}g:\{0,1\}^m\to\{0,1\}g:{0,1}m→{0,1}, [ \widetilde{deg}(f\circ g) = Θ!\left( \widetilde{deg}(f),\widetilde{deg}(g) \right), ] where deg~\widetilde{deg}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.
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 fff and ggg, deg⁡~(f∘g)=Ω(deg⁡~(f)deg⁡~(g))\widetilde{\deg}(f\circ g)=\Omega(\widetilde{\deg}(f)\widetilde{\deg}(g))deg​(f∘g)=Ω(deg​(f)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∘gf\circ gf∘g over parameterized input distributions. A dual witness for ggg defines a degree-filtered operator whose unitary evolution produces probability distributions with derivative scale Θ(deg⁡~(g))\Theta(\widetilde{\deg}(g))Θ(deg​(g)). Averaging preserves boundedness and converts polynomial degree into a bound on total trigonometric frequency. Squarefree extraction recovers an approximation to fff; bounds on homogeneous Taylor components show that insufficient degree would permit truncation below deg⁡~(f)\widetilde{\deg}(f)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 QE(f∘ORm)=O(mdeg⁡(f)+n2m)Q_E(f\circ\mathrm{OR}_m)=O(m\deg(f)+n^2\sqrt m)QE​(f∘ORm​)=O(mdeg(f)+n2m​) by coherently correcting bounded-error computations. For explicit recursively composed functions on 4k4^k4k bits and mk=64km_k=64^kmk​=64k, the composed complexity is O(128k)O(128^k)O(128k), whereas the product of the individual exact complexities is Ω(160k)\Omega(160^k)Ω(160k). Their ratio is therefore O((4/5)k)O((4/5)^k)O((4/5)k) and tends to zero.
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→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} and g:{0,1}m→{0,1}g:\{0,1\}^m\to\{0,1\}g:{0,1}m→{0,1}, deg~(f∘g)=Θ ⁣(deg~(f) deg~(g)), \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), deg​(f∘g)=Θ(deg​(f)deg​(g)), where deg~\widetilde{deg}deg​ denotes constant-error approximate degree. Source: http://arxiv.org/abs/2609.30139v1 (arXiv:2609.30139v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
For any Boolean functions f and g, the question whether R(f∘g)=Θ~(R(f)⋅R(g))\text {R}(f\circ g) = \tilde{\Theta }(\text {R}(f) \cdot \text {R}(g))R(f∘g)=Θ~(R(f)⋅R(g)) is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether deg~(f∘g)=Θ~(deg~(f)⋅deg~(g))\widetilde{\text {deg}}(f\circ g) = \tilde{\Theta }(\widetilde{\text {deg}}(f)\cdot \widetilde{\text {deg}}(g))deg​(f∘g)=Θ~(deg​(f)⋅deg​(g)) . These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which R\text {R}R and deg~\widetilde{\text {deg}}deg​ compose. A recent landmark result (Ben-David and Blais, 2020) showed that R(f∘g)=Ω(noisyR(f)⋅R(g))\text {R}(f \circ g) = \Omega (\text {noisyR}(f)\cdot \text {R}(g))R(f∘g)=Ω(noisyR(f)⋅R(g)) . This implies that composition holds iff noisyR(f)=Θ~(R(f))\text {noisyR}(f) = \tilde{\Theta }(\text {R}(f))noisyR(f)=Θ~(R(f)) . We show two results: On the other hand, we prove that deg~(f∘g)=Ω~(bs(f)⋅deg~(g)), \widetilde{\text {deg}}(f\circ g) = \widetilde{\Omega }(\sqrt{\text {bs}(f)} \cdot \widetilde{\text {deg}}(g)), deg​(f∘g)=Ω(bs(f)​⋅deg​(g)), where bs(f)\text {bs}(f)bs(f) is the block sensitivity of f. This implies that deg~\widetilde{\text {deg}}deg​ composes when deg~(f)\widetilde{\text {deg}}(f)deg​(f) is asymptotically equal to bs(f)\sqrt{\text {bs}(f)}bs(f)​ . It is already known that both R\text {R}R and deg~\widetilde{\text {deg}}deg​ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.
For bounded-error randomized query complexity, we resolve the composition conjecture up to logarithmic factors. The general upper bound R(f∘g)=O ⁣(R(f)R(g)log⁡(R(f)+1))R(f\circ g) = O\!\left(R(f)R(g)\log(R(f)+1)\right)R(f∘g)=O(R(f)R(g)log(R(f)+1)) was already known. Although Meiburg recently disproved constant-factor multiplicative composition for total Boolean functions, the conjecture allowing polylogarithmic losses remained open. We settle this question by proving that, for all (possibly partial) Boolean functions fff and ggg, R(f∘g)=Ω ⁣(R(f)R(g)log⁡(n+1)), R(f\circ g) = Ω\!\left(\frac{R(f)R(g)}{\log(n+1)}\right), R(f∘g)=Ω(log(n+1)R(f)R(g)​), where nnn is the input size for fff.
We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function f on N bits, define F(x_1,...,x_M) = OMB(f(x_1),...,f(x_M)) to be the function on M*N bits obtained by block-composing f with a function known as ODD-MAX-BIT. We show that, if f requires large degree to approximate to error 2/3 in a certain one-sided sense (captured by a complexity measure known as positive one-sided approximate degree), then F requires large degree to approximate even to error 1-2^{-M}. This generalizes a result of Beigel (Computational Complexity, 1994), who proved an identical result for the special case f=OR. Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions F that have low threshold degree. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function. We describe several applications, including improved separations between the complexity classes P^{NP} and PP in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e.~functions obtained by composing a base function with itself a number of times. Let hdh^dhd denote the standard ddd-fold composition of the base function hhh. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: (I) The outer function f:{0,1}n→{0,1}f:\{0,1\}^n\to \{0,1\}f:{0,1}n→{0,1} is a recursive function of the form hdh^dhd, with hhh being any base function and d=Ω(log⁡log⁡n)d= Ω(\log\log n)d=Ω(loglogn). (II) The inner function is a recursive function of the form hdh^dhd, with hhh being any constant arity base function (other than AND and OR) and d=Ω(log⁡log⁡n)d= Ω(\log\log n)d=Ω(loglogn), where nnn is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be \emph{efficiently eliminated} if the inner or outer function is a recursive function.
We study exact quantum algorithms for block compositions of total Boolean functions. For an outer function fff of degree DDD and an inner function ggg on mmm bits, we prove QE(f∘g)=O ⁣(mD+QE(f)Q1/(4D)(g)). Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right). QE​(f∘g)=O(mD+QE​(f)Q1/(4D)​(g)). The algorithm combines approximate inner evaluations with a finite exact correction. Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction. We first establish the construction with an arity-dependent error threshold and then obtain the degree-dependent threshold above. For recursive ternary not-all-equal, this gives an exact algorithm using (3/2)k(1+o(1))(3/\sqrt2)^{k(1+o(1))}(3/2​)k(1+o(1)) queries asymptotically. More generally, for every fixed nonconstant total gadget hhh, we determine the exact recursive rate as max⁡{deg(h),Adv⁡±(h)}\max\{\textrm{deg}(h),\operatorname{Adv}^{\pm}(h)\}max{deg(h),Adv±(h)} and prove QE(h∘k)=O~h(R(h∘k)2)Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2)QE​(h∘k)=Oh​(R(h∘k)2). The composition limit also allows to transfer separations from QεQ_{\varepsilon}Qε​ and °°° to exact quantum query complexity QEQ_EQE​ (similar to fractional block sensitivity to block sensitivity transfer in Tal and Kulkarni 2016, Chicago Journal of Theoretical Computer Science). We construct a family with s=bs⁡=fbs⁡≥QE3/2−o(1)s=\operatorname{bs}=\operatorname{fbs}\ge Q_E^{3/2-o(1)}s=bs=fbs≥QE3/2−o(1)​, improving the previous exponent 1.1527…1.1527\ldots1.1527…. A second construction gives R≥QE2−o(1)R \ge Q_E^{2-o(1)}R≥QE2−o(1)​, improving the previous exponent 3/23/23/2. We also allow different inner functions and give analogous quantitative separations in quantum communication.