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:2601.08073

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

cs.CCquant-phSubmitted Jan 12, 2026• Announced Jan 14, 2026• 0 citations
arXivHTMLPDF

Abstract

For a (possibly partial) Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}$. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^*(f)=\max\{R^*(f),C^*(f)\}$. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.

Comments
25 pages

Related papers

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

For a (possibly partial) Boolean function f:{0,1}n→{0,1} as well as a query complexity measure M which maps Boolean functions to real numbers, define the composition limit of M on f by M*(f)=limk→∞ M(fk)1/k.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•0 citations

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Miklós Sántha, Dmitry Gavinsky, Troy Lee +1 more

Let $R_\epsilon(\cdot)$ stand for the bounded-error randomized query complexity with error $\epsilon > 0$. For any relation $f \subseteq \{0,1\}^n \times S$ and partial Boolean function $g \subseteq \{0,1\}^m \times \{0,1\}$, we show that $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \sqrt{R_{1/3}(g)})$, where $f \circ g^n \subseteq (\{0,1\}^m)^n \times S$ is the composition of $f$ and $g$. We give an example of a relation $f$ and partial Boolean function $g$ for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity $\bar \chi(g)$ of a partial Boolean function $g$. We show $\bar \chi(g) \in \Omega(\sqrt{R_{1/3}(g)})$ for any (partial) function $g$ and $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \bar \chi(g))$; these two bounds imply our composition result. We further show that $\bar \chi(g)$ is always at least as large as the sabotage complexity of $g$, introduced by Ben-David and Kothari.

•Jan 1, 2019•0 citations

Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity

Andris Ambainis, Jānis Iraids, Martins Kokainis

We study how large the certificate complexity ${C}(f)$ of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function $f$ whose randomized query complexity with one-sided error satisfies ${R}_1(f) = Θ(\sqrt{{C}(f)})$. This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function $F$ with bounded-error quantum query complexity ${Q}(F) = \widetilde O({C}(F)^{1/4})$, attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are $\widetilde O(\sqrt{{C}(F)})$. We also prove matching lower bounds for these two measures on $F$.

quant-pharXiv:2609.11664•Sep 11, 2026•0 citations

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions

Shalev Ben-David, Eric Blais

We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions $f$ and $g$ such that $R(f\circ g)\ll R(f) R(g)$. In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of $f$). Second, we show that for all $f$ and $g$, $R(f\circ g)=Ω(\mathop{noisyR}(f)\cdot R(g))$, where $\mathop{noisyR}(f)$ is a measure describing the cost of computing $f$ on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure $M(\cdot)$ satisfying $R(f\circ g)=Ω(M(f)R(g))$ for all $f$ and $g$, it must hold that $\mathop{noisyR}(f)=Ω(M(f))$ for all $f$. We also give a clean characterization of the measure $\mathop{noisyR}(f)$: it satisfies $\mathop{noisyR}(f)=Θ(R(f\circ gapmaj_n)/R(gapmaj_n))$, where $n$ is the input size of $f$ and $gapmaj_n$ is the $\sqrt{n}$-gap majority function on $n$ bits.

arXiv:2002.10809•Feb 25, 2020•6 citations

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Dmitry Gavinsky, Troy Lee, Miklós Sántha +1 more

For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.

arXiv:1811.10752•Leibniz international proceedings in informatics•Nov 27, 2018•4 citations

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract

Shalev Ben-David, Eric Blais

We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions f and g such that R(f°g) ≪ R(f)R(g). In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of f). Second, we show that for all f and g, R(f°g) = Ω(noisyR(f) R(g)), where noisyR(f) is a measure describing the cost of computing f on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure M(·) satisfying R(f°g)=Ω(M(f)R(g)) for all f and g, it must hold that noisyR(f)=Ω(M(f)) for all f. We also give a clean characterization of the measure noisyR(f): it satisfies noisyR(f)=Θ(R(f°GapMajn)/R(GapMajn)), where n is the input size of f and GapMajn is the √n-gap majority function on n bits.

Annual Symposium on Foundations of Computer Science•Nov 1, 2020•9 citations
For a (possibly partial) Boolean function f ⁣:{0,1}n→{0,1}f\colon\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} as well as a query complexity measure MMM which maps Boolean functions to real numbers, define the composition limit of MMM on fff by M∗(f)=lim⁡k→∞M(fk)1/kM^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}M∗(f)=limk→∞​M(fk)1/k.
We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show R0∗(f)=max⁡{R∗(f),C∗(f)}R_0^*(f)=\max\{R^*(f),C^*(f)\}R0∗​(f)=max{R∗(f),C∗(f)}. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability.
Along the way, we prove various combinatorial properties of measures and composition limits.
Let Rϵ(⋅)R_\epsilon(\cdot)Rϵ​(⋅) stand for the bounded-error randomized query complexity with error ϵ>0\epsilon > 0ϵ>0. For any relation f⊆{0,1}n×Sf \subseteq \{0,1\}^n \times Sf⊆{0,1}n×S and partial Boolean function g⊆{0,1}m×{0,1}g \subseteq \{0,1\}^m \times \{0,1\}g⊆{0,1}m×{0,1}, we show that R1/3(f∘gn)∈Ω(R4/9(f)⋅R1/3(g))R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \sqrt{R_{1/3}(g)})R1/3​(f∘gn)∈Ω(R4/9​(f)⋅R1/3​(g)​), where f∘gn⊆({0,1}m)n×Sf \circ g^n \subseteq (\{0,1\}^m)^n \times Sf∘gn⊆({0,1}m)n×S is the composition of fff and ggg. We give an example of a relation fff and partial Boolean function ggg for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity χˉ(g)\bar \chi(g)χˉ​(g) of a partial Boolean function ggg. We show χˉ(g)∈Ω(R1/3(g))\bar \chi(g) \in \Omega(\sqrt{R_{1/3}(g)})χˉ​(g)∈Ω(R1/3​(g)​) for any (partial) function ggg and R1/3(f∘gn)∈Ω(R4/9(f)⋅χˉ(g))R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \bar \chi(g))R1/3​(f∘gn)∈Ω(R4/9​(f)⋅χˉ​(g)); these two bounds imply our composition result. We further show that χˉ(g)\bar \chi(g)χˉ​(g) is always at least as large as the sabotage complexity of ggg, introduced by Ben-David and Kothari.
We study how large the certificate complexity C(f){C}(f)C(f) of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function fff whose randomized query complexity with one-sided error satisfies R1(f)=Θ(C(f)){R}_1(f) = Θ(\sqrt{{C}(f)})R1​(f)=Θ(C(f)​). This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function FFF with bounded-error quantum query complexity Q(F)=O~(C(F)1/4){Q}(F) = \widetilde O({C}(F)^{1/4})Q(F)=O(C(F)1/4), attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are O~(C(F))\widetilde O(\sqrt{{C}(F)})O(C(F)​). We also prove matching lower bounds for these two measures on FFF.
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions fff and ggg such that R(f∘g)≪R(f)R(g)R(f\circ g)\ll R(f) R(g)R(f∘g)≪R(f)R(g). In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of fff). Second, we show that for all fff and ggg, R(f∘g)=Ω(noisyR(f)⋅R(g))R(f\circ g)=Ω(\mathop{noisyR}(f)\cdot R(g))R(f∘g)=Ω(noisyR(f)⋅R(g)), where noisyR(f)\mathop{noisyR}(f)noisyR(f) is a measure describing the cost of computing fff on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure M(⋅)M(\cdot)M(⋅) satisfying R(f∘g)=Ω(M(f)R(g))R(f\circ g)=Ω(M(f)R(g))R(f∘g)=Ω(M(f)R(g)) for all fff and ggg, it must hold that noisyR(f)=Ω(M(f))\mathop{noisyR}(f)=Ω(M(f))noisyR(f)=Ω(M(f)) for all fff. We also give a clean characterization of the measure noisyR(f)\mathop{noisyR}(f)noisyR(f): it satisfies noisyR(f)=Θ(R(f∘gapmajn)/R(gapmajn))\mathop{noisyR}(f)=Θ(R(f\circ gapmaj_n)/R(gapmaj_n))noisyR(f)=Θ(R(f∘gapmajn​)/R(gapmajn​)), where nnn is the input size of fff and gapmajngapmaj_ngapmajn​ is the n\sqrt{n}n​-gap majority function on nnn bits.
For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions f and g such that R(f°g) ≪ R(f)R(g). In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of f). Second, we show that for all f and g, R(f°g) = Ω(noisyR(f) R(g)), where noisyR(f) is a measure describing the cost of computing f on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure M(·) satisfying R(f°g)=Ω(M(f)R(g)) for all f and g, it must hold that noisyR(f)=Ω(M(f)) for all f. We also give a clean characterization of the measure noisyR(f): it satisfies noisyR(f)=Θ(R(f°GapMajn)/R(GapMajn)), where n is the input size of f and GapMajn is the √n-gap majority function on n bits.