Q The Query Complexity Zoo
\(\mathrm{R}^{*}(f)\)

Asymptotic composition rate

lim_k R(f^{o k})^{1/k}: the per-level cost of composing f with itself many times.

Definition

$\mathrm{R}^{*}(f)=\lim_{k\to\infty}\mathrm{R}(f^{\circ k})^{1/k}$ is the per-level cost of iterated composition. The limit exists; bounded-error amplification requires care, so it is not justified by plain submultiplicativity of R. The composition rate can exceed one-level complexity: \(H_q\) attains $\mathrm{R}^{*}/\mathrm{R}=\Theta(\log\mathrm{R})$ [Meiburg26composition].

Basic facts

  • $\mathrm{R}^*(f) \ge \Omega(\mathrm{LR}(f))$ [BBGM22].
  • $\mathrm{R}^*(f) \ge \Omega(\mathrm{Q}(f))$, since quantum query complexity composes perfectly.
  • Whether either bound dominates the other is open.
  • General upper bound: $\mathrm{R}^{*}(f)=O(\mathrm{R}(f)\log(\mathrm{R}(f)+1))$; a total family attains it [Meiburg26composition, Theorem 10.7].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{R}^{*}(f)\). “\(\mathrm{R}^{*}(f)\) in terms of it” is the pair with \(\mathrm{R}^{*}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\mathrm{R}^{*}(f)\) in terms of it It in terms of \(\mathrm{R}^{*}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 open pair → total1,2 partial1,? derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total2,4 partial2,? open pair → total1,1 partial1,? derived open pair →
\(\mathrm{LR}(f)\) Linearised randomized complexity total1,2 partial1,2 derived open pair → total1,1 partial1,? open pair →
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity total1,3 partial1,? derived open pair → total1,2 partial1,? derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
AND total \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
PARITY total \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
MAJORITY total \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Threshold total \(\Theta(n)\) Squeezed: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$. BBGM22
Symmetric functions (general) total \(\Theta(n)\) Sandwiched: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
ODD-MAX-BIT total \(\Theta(n)\) Sandwiched: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
ADDRESS / multiplexer total \(\Theta(k+1)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
Binary tree navigation total \(\Theta(k)\) Sandwiched: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(k)$ here. BBGM22
TRIBES total \(\Theta(n)\) Sandwiched: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
AND-OR tree (depth 2) total \(\Omega(n),\ O(n^2)\) The asymptotic composition rate obeys $\max\{\mathrm{Q},\ \Omega(\mathrm{LR})\} \le \mathrm{R}^{*} \le \mathrm{R}$ [BBGM22], and $\mathrm{Q} = \Theta(n)$, $\mathrm{R} = \Theta(n^2)$. Self-composing $\mathrm{AND}_n\circ\mathrm{OR}_n$ produces the balanced alternating $\mathrm{AND}/\mathrm{OR}$ tree of fan-in $n$, so $\mathrm{R}^{*}$ here is precisely the per-level randomized cost of deep read-once $\mathrm{AND}/\mathrm{OR}$ formulas: the same phenomenon that drops \(\bar{\wedge}\text{-tree}\) from exponent $1$ to $0.753$. BBGM22
NAND tree (balanced AND-OR formula) total \(\big(\tfrac{1+\sqrt{33}}{4}\big)^{d} = N^{0.753\ldots}\) One of the few entries in the zoo that is a number rather than a $\Theta$-class. Because $(\mathrm{NANDtree}_d)^{\circ k} = \mathrm{NANDtree}_{dk}$ and $\mathrm{R}(\mathrm{NANDtree}_h) = \Theta(\alpha^h)$ with $\alpha = (1+\sqrt{33})/4 = 1.68614\ldots$, taking the $k$-th root kills the hidden constant exactly and leaves $\alpha^d$. Read-once formulas are the case where randomized query complexity does compose perfectly, so $\mathrm{R}^{*} = \mathrm{R}$ here up to the constant. SaksWigderson86 Santha95
Recursive MAJORITY-of-3 total \(\alpha^{d},\ \alpha \in [2.59,\ 2.64944]\) As for \(\bar{\wedge}\text{-tree}\), self-composition makes $\mathrm{R}^{*}$ the exact base of the exponential; pinning $\alpha$ is the open problem on recursive majority. GoosJayram16 MNSSTX16
Kushilevitz's function (iterated) total \(\Theta(N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $N$ here.
Rubinstein's function total \(\Theta(N)\) putative Block sensitivity is supermultiplicative, so $\mathrm{R}(f^{\circ m}) \ge \mathrm{bs}(f)^m$ and $\mathrm{R}^{*} \ge \mathrm{bs} = N/2$; and $\mathrm{R}^{*} \le \mathrm{R} = \Theta(N)$ by submultiplicativity. Composition is perfect here for the trivial reason that $\mathrm{bs}$ and $\mathrm{R}$ already agree.
Ambainis-Sun function total \(\Theta(N)\) putative Block sensitivity is supermultiplicative, so $\mathrm{R}(f^{\circ m}) \ge \mathrm{bs}(f)^m$ and $\mathrm{R}^{*}(f) \ge \mathrm{bs}(f) = \Theta(N)$; and $\mathrm{R}^{*} \le \mathrm{R} = \Theta(N)$ by submultiplicativity. Composition is therefore perfect here for the trivial reason that $\mathrm{bs}$ and $\mathrm{R}$ already coincide.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative Block sensitivity is supermultiplicative under composition, so $\mathrm{R}(f_d^{\circ m}) \ge \mathrm{bs}(f_d^{\circ m}) \ge \mathrm{bs}(f_d)^m$ for every $m$; taking $m$-th roots gives $\mathrm{R}^{*}(f_d) \ge \mathrm{bs}(f_d) \ge 14011^{\,d}$. The same computation makes $\mathrm{R}^{*}$ multiplicative along this family, since $f_d$ is itself the $d$-fold self-composition of the base function.
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $f_{2m,m}$: squeezed between $\mathrm{LR}=\widetilde\Theta(\sqrt n)$ and $\mathrm{R}=\widetilde O(\sqrt n)$. The quantum floor $\mathrm{R}^*\ge\Omega(\mathrm{Q})=\widetilde\Omega(n^{1/4})$ is weaker.
Cheat-sheet functions total \(\widetilde\Theta(n)\) Unlike $\mathrm{LR}$ and $\bar\chi$, the quantum-aware relaxation is pinned: $\mathrm{R}^*\ge\Omega(\mathrm{Q})=\widetilde\Omega(n)$ and $\mathrm{R}^*\le\mathrm{R}=\widetilde O(n)$. So the cheat-sheet hardness is visible to $\mathrm{R}^*$ even though it may be invisible to the purely classical relaxations above.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Unlike the classical relaxations above, this one is pinned at the top by the quantum floor $\mathrm{R}^*\ge\Omega(\mathrm{Q})=\widetilde\Omega(n^3)$, and $\mathrm{R}^*\le\mathrm{R}$ costs nothing since $\mathrm{R}$ is itself only bounded below.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Squeezed between $\mathrm{LR}=\widetilde\Omega(n^{4/3})$ and $\mathrm{R}=\widetilde O(n^2)$; the quantum floor $\mathrm{R}^*=\Omega(\mathrm{Q})=\widetilde\Omega(n^{2/3})$ is weaker.
Gilmer-Saks-Srinivasan functions total \(\Omega(n),\ O(n^2)\) Squeezed between $\mathrm{LR}=\Omega(n)$ and $\mathrm{R}=O(n^2)$; the quantum floor $\mathrm{R}^*=\Omega(\mathrm{Q})=\Omega(\sqrt n)$ is weaker.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Squeezed between $\mathrm{LR}=\widetilde\Omega(\sqrt n)$ and $\mathrm{R}=\widetilde O(n)$; the quantum floor $\mathrm{R}^*=\Omega(\mathrm{Q})=\widetilde\Omega(n^{1/4})$ is weaker.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) Squeezed between $\mathrm{LR}=\widetilde\Omega(n^{1/3})$ and $\mathrm{R}=\widetilde\Theta(n^{2/3})$; the quantum floor $\mathrm{R}^*=\Omega(\mathrm{Q})=\widetilde\Omega(n^{1/6})$ is weaker.
Ambainis' exact-quantum function total \(\Theta(3^d)\) Squeeze: $\mathrm{LR}=O(\mathrm{R}^{*})$ and $\mathrm{R}^{*}\le\mathrm{R}$ [BBGM22], both $\Theta(3^d)$. Iterating buys nothing, which is no surprise: $\mathrm{NE}^d$ is already an iterate, and $\mathrm{R}$ is exactly the arity at every depth. BBGM22
FORRELATION partial \(\widetilde O(\sqrt n)\) $\mathrm{R}^{*} \le \mathrm{R}$ for partial $f$; from below $\mathrm{R}^{*} = \Omega(\mathrm{LR}) = \widetilde\Omega(n^{1/4})$ and $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(1)$, so the composition-friendly version of $\mathrm{R}$ is still polynomially far above the single quantum query.
k-FORRELATION partial \(\widetilde O\!\big(n^{1-1/k}\big)\) $\mathrm{R}^{*} \le \mathrm{R}$; from below $\mathrm{R}^{*} = \Omega(\mathrm{LR}) = \widetilde\Omega(n^{1/2-1/(2k)})$.
Simon's problem partial \(O(2^{n/2})\) $\mathrm{R}^{*} \le \mathrm{R}$; from below $\mathrm{R}^{*} = \Omega(\mathrm{LR}) = \Omega(2^{n/4})$ and $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(n)$.
Deutsch-Jozsa partial \(\Theta(1)\) Sandwiched: $\Omega(\mathrm{Q}) \le \mathrm{R}^{*} \le \mathrm{R} = O(1)$.
Bernstein-Vazirani partial \(O(n)\) $\mathrm{R}^{*} \le \mathrm{R} = O(n)$; from below only $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(1)$, since quantum query complexity composes perfectly. ($\mathrm{LR} = O(\mathrm{R}^{*})$ is recorded only for total $f$.)
Dense marked bit partial \(\Theta(1)\) Sandwiched: $\Omega(\mathrm{Q}) \le \mathrm{R}^{*} \le \mathrm{R} = \Theta(1)$.
Gap-Majority partial \(O(\min(n, 1/\delta^2))\) $\mathrm{R}^{*} \le \mathrm{R}$, and $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(\min(n,1/\delta))$ because quantum query complexity composes perfectly. Whether the limit sits at $\mathrm{R}$ or at $\mathrm{Q}$ is exactly the open question of [BBGM22].
Gap-Majority at constant gap partial \(O(1)\) $\mathrm{R}^{*} \le \mathrm{R}$.
Approximate index partial \(O(\sqrt{k\log k})\) $\mathrm{R}^{*} \le \mathrm{R}$; the lower bound $\mathrm{R}^{*} = \Omega(\mathrm{LR})$ is recorded only for total $f$, and $\mathrm{R}^{*} = \Omega(\mathrm{Q})$ gives nothing without a $\mathrm{Q}$ lower bound.
Collision problem partial \(\Omega(n^{1/3})\) $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(n^{1/3})$ since quantum query complexity composes perfectly, and $\mathrm{R}^{*} \le \mathrm{R} = O(\sqrt n)$. Whether iterated collision-finding costs $n^{1/3}$ or $n^{1/2}$ per level is open.
Element distinctness total \(\Theta(n)\) $\mathrm{R}^* \ge \Omega(\mathrm{LR}) = \Omega(n)$ and $\mathrm{R}^* \le \mathrm{R} = O(n)$, so repeated self-composition loses nothing. BBGM22
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) $\mathrm{R}^* \ge \Omega(\mathrm{Q}) = \Omega(n^{1/3})$, since quantum query complexity composes perfectly -- a chain that, unlike $\mathrm{R}^* = \Omega(\mathrm{LR})$, is available for partial functions.
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
$k$-distinctness total \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) Sandwiched: $\mathrm{R}^{*}(f) = \Omega(\mathrm{LR}(f))$ and $\mathrm{R}^{*}(f) \le \mathrm{R}(f)$, with both ends $\Theta(m^3)$ here. So iterating $\mathrm{MP}$ costs the full $\mathrm{R}$ per level.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
Scorpion graphs total \(\Theta(m)\) Squeezed between $\mathrm{LR} = \Theta(m)$ and $\mathrm{R} = \Theta(m)$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Squeezed between $\mathrm{LR} = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^2)$.
Meiburg’s maximal composition-rate separation total \(\Theta(q^5\log^2 q)\) Meiburg26composition