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

Robust quantum query complexity

Quantum queries when the oracle is noisy (each query answer is corrupted).

Definition

The quantum analogue of the \(\mathrm{N}_{p}(f)\) model: the oracle returns a corrupted bit, or more precisely the algorithm has access to a "noisy" version of $x$ and must be robust to it. Buhrman-Newman-Röhrig-de Wolf showed that $n$ noisy quantum queries suffice to recover all $n$ bits with high probability.

Parameters

\(p\) (p) default \(constant\)

Basic facts

  • $\mathrm{Q}^{\mathrm{rob}}(\mathrm{PARITY}_n) = \Theta(n)$ -- no $\log n$ overhead, in contrast to the classical $\Theta(n\log n)$ [FRPU94 vs BNRdW05].
  • $\mathrm{Q}^{\mathrm{rob}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$ in general; whether the log is needed is open.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Q}^{\mathrm{rob}}(f)\). “\(\mathrm{Q}^{\mathrm{rob}}(f)\) in terms of it” is the pair with \(\mathrm{Q}^{\mathrm{rob}}(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{Q}^{\mathrm{rob}}(f)\) in terms of it It in terms of \(\mathrm{Q}^{\mathrm{rob}}(f)\)
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1 partial1,1 relation1,1 open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity total1,1 partial1,1 relation1,1 derived open pair → total3,4 partial∞ relation∞ derived open pair →
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity total1,3 partial1,? relation1,? derived open pair → total2,4 partial2,? relation2,? derived open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(\sqrt n)\) Robust Grover: search over bounded-error inputs costs $O(\sqrt n)$ with no log factor, by amplitude amplification around a subroutine whose error is never amplified. Classically, noisy OR costs $\Theta(n)$ either way, so the quantum speedup survives noise intact. HoyerMoscadeWolf03 BNRdW05
AND total \(\Theta(\sqrt n)\) Robust Grover search for a zero costs $O(\sqrt n)$ with no log factor, and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt n)$. The \(\mathrm{OR}_n\) entry after negating the input bits. HoyerMoscadeWolf03 BNRdW05
PARITY total \(\Theta(n)\) The headline robustness result: $n$ noisy quantum queries recover all $n$ bits, so $\mathrm{Q}^{\mathrm{rob}} = O(n)$, matching $\mathrm{Q} = n/2$ up to a constant. Classically the same task costs $\Theta(n\log n)$ [FRPU94] -- noise imposes a logarithmic tax on randomized algorithms that quantum algorithms simply do not pay. An explicit degree-$O(n)$ robust polynomial was later given by [Sherstov13robust]. BNRdW05 FRPU94
MAJORITY total \(\Theta(n)\) Sandwiched between $\mathrm{Q} = \Theta(n)$ and the universal $O(n)$ upper bound. BNRdW05
Threshold total \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) Theorem 4 of [BNRdW05] gives a robust quantum algorithm using $O(\sqrt{n(n-\Gamma(f)+1)})$ queries for every symmetric $f$; here $\Gamma = |2k-n-1|$, so $n - \Gamma + 1$ is $2k$ for $k \le (n+1)/2$ and $2(n-k+1)$ otherwise, and the bound reads $O(\sqrt{k(n-k+1)})$. That matches $\mathrm{Q}$ from above, and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q}$. So noise is free for the quantum algorithm at every $k$, while classically it costs a $\log$ factor at $k \approx n/2$. BNRdW05
Symmetric functions (general) total \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) Same as the recorded $\mathrm{Q}$, since $n - \Gamma(f) \ge 1$ for non-constant $f$. Theorem 4 of [BNRdW05]: for every symmetric $f$ there is a robust quantum algorithm using $O(\sqrt{n(n-\Gamma(f)+1)})$ queries -- robust counting suffices, since $f$ is constant on the middle band of weights of width $\Gamma(f)$. The matching lower bound is $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt{n(n-\Gamma(f))})$ by Paturi (the \(\mathrm{Q}_{\varepsilon}(f)\) line). So the whole symmetric family tolerates noisy inputs for free, in contrast with the classical $\log$ tax at \(\oplus_n\) and \(\mathrm{MAJ}_n\). BNRdW05
EXACT-HALF total \(\Theta(n)\) Sandwiched between $\mathrm{Q} = \Theta(n)$ and the universal $O(n)$ robust upper bound. BNRdW05
ODD-MAX-BIT total \(\Omega(\sqrt n),\ O(n)\) Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt n)$. Upper: the universal $O(n)$ bound of [BNRdW05] for recovering all $n$ noisy bits. Whether the $\sqrt n$ algorithm survives noise is the interesting question and is not settled here. BNRdW05
ADDRESS / multiplexer total \(\Omega(k),\ O(k\log k)\) Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(k)$. Upper: read the address and the entry classically, repeating each query $O(\log k)$ times. The universal $O(\mathrm{arity})$ bound of [BNRdW05] is useless here, the arity being $k+2^k$. BNRdW05
Binary tree navigation total \(\Omega(k),\ O(k\log k)\) Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(k)$. Upper: run the depth-$k$ walk classically, repeating each query $O(\log k)$ times. The universal $O(\mathrm{arity})$ bound of [BNRdW05] is useless here, since the arity is $2^k-1$; whether the $\log k$ can be removed is exactly the open case of robust computation for very shallow, very wide functions. BNRdW05
TRIBES total \(\Theta(\sqrt n)\)· putative At least $\mathrm{Q} = \Omega(\sqrt n)$. The matching upper bound is the ordinary $\sqrt s \cdot \sqrt w$ algorithm with both Grover layers replaced by robust amplitude amplification, which tolerates bounded-error inputs with no log overhead. So the quantum speedup over $\mathrm{R} = \Theta(n)$ survives noisy oracles intact. HoyerMoscadeWolf03 BNRdW05
AND-OR tree (depth 2) total \(\Theta(n) = \Theta(\sqrt N)\)· Lower bound $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(n)$. Upper bound: Grover search on bounded-error inputs costs $O(\sqrt m)$ calls with no logarithmic overhead [HoyerMoscadeWolf03], and noisy oracle access to a block can be turned into bounded-error access at constant amortised cost [BNRdW05]. Run robust search inside each $\mathrm{OR}_n$ block ($O(\sqrt n)$ noisy queries) and robust search again at the outer $\mathrm{AND}_n$ over the $n$ bounded-error block answers ($O(\sqrt n)$ calls): $O(n)$ in total. HoyerMoscadeWolf03 BNRdW05
NAND tree (balanced AND-OR formula) total \(\Omega(\sqrt N),\ O(\sqrt N\log N)\) $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt N)$, and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ in general [BNRdW05]. Whether the logarithm can be removed for the NAND tree is open; it can be for \(\oplus_n\). BNRdW05
Recursive MAJORITY-of-3 total \(\Omega(2^{\,d}),\ O(d\,2^{\,d})\) $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(2^d)$ and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05]. Unlike the classical side, the quantum value is pinned to within the logarithm because $\mathrm{Q} = \Theta(2^d)$ is exact [Reichardt11]. BNRdW05
Kushilevitz's function (iterated) total \(\Omega(\sqrt N),\ O(N)\) Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(\sqrt N)$. Upper: $N$ noisy quantum queries recover the whole input with high probability [BNRdW05], so $\mathrm{Q}^{\mathrm{rob}} = O(N)$ for any function; this beats $O(\mathrm{Q}\log \mathrm{Q})$ because $\mathrm{Q}$ itself is only known up to an $N^{0.11}$ window here. BNRdW05
Rubinstein's function total \(\Omega(\sqrt N),\ O(\sqrt N\log N)\) $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt N)$ and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05]. BNRdW05
Ambainis-Sun function total \(\Omega(\sqrt N),\ O(N^{3/4}\log N)\) $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(\sqrt N)$ and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05], with the recorded $\mathrm{Q} = O(N^{3/4})$. The window is inherited wholesale from the open $\mathrm{Q}$ window. BNRdW05
AND composed with NOT-EXACT-HALF total \(\Omega(n^{3/2}),\ O(n^{3/2}\log n)\) $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(n^{3/2})$, and $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05]. The generic $O(N) = O(n^2)$ bound of [BNRdW05] is weaker. BNRdW05
Meiburg's tournament-subcube function total \(\Omega(118.3^{\,d})\) putative A robust quantum algorithm works in particular with a clean oracle, so $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(118.3^{\,d})$. The generic upper bound $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05] is vacuous here, since no upper bound on $\mathrm{Q}$ is known. BNRdW05
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $f_{2m,m}$: $\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05] applied to $\mathrm{Q}=\widetilde O(n^{1/4})$. BNRdW05
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05] with $\mathrm{Q}=\widetilde\Theta(n)$. BNRdW05
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{Q}^{\mathrm{rob}}\ge\mathrm{Q}=\widetilde\Omega(n^3)$ [BNRdW05]. BNRdW05
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3}),\ \widetilde O(n^2)\) Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], inheriting the $\mathrm{Q}$ range. BNRdW05
Gilmer-Saks-Srinivasan functions total \(\Omega(\sqrt n)\) Squeeze: $\mathrm{Q}^{\mathrm{rob}}\ge\mathrm{Q}=\Omega(\sqrt n)$ [BNRdW05]. BNRdW05
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n)\) Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], inheriting the $\mathrm{Q}$ range $[\widetilde\Omega(n^{1/4}),\widetilde O(n)]$. BNRdW05
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6}),\ \widetilde O(n^{2/3})\) Squeeze: $\mathrm{Q}\le\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], inheriting the $\mathrm{Q}$ range. BNRdW05
Ambainis' exact-quantum function total \(\widetilde\Theta(2.1213^d)\) Squeeze: $\mathrm{Q}^{\mathrm{rob}}\ge\mathrm{Q}$ and $\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ [BNRdW05], with $\mathrm{Q}=\Theta(2.1213^d)$. BNRdW05
FORRELATION partial \(\Theta(1)\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$, and $\mathrm{Q} = 1$. So even an oracle whose every answer is only a bounded-error bit is beaten by $O(1)$ quantum queries, against $\mathrm{R} = \widetilde\Theta(\sqrt n)$ and $\mathrm{N}_p = \widetilde\Theta(\sqrt n)$ classically.
k-FORRELATION partial \(O(k\log k)\) The generic robustification bound $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$ applied to $\mathrm{Q} = \lceil k/2\rceil$; and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q}$. Still independent of $n$.
Simon's problem partial \(\widetilde\Theta(n)\) Between $\mathrm{Q} = \Theta(n)$ and $\mathrm{Q}\log\mathrm{Q} = O(n\log n)$. So the exponential separation survives a noisy oracle.
Deutsch-Jozsa partial \(\Theta(1)\) At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = 1$.
Bernstein-Vazirani partial \(\Theta(1)\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ with $\mathrm{Q} = 1$, so a robust oracle costs only a constant here.
Unstructured search (relation) relation \(\Theta(\sqrt n)\)· Grover search is robust: $O(\sqrt n)$ queries still suffice when each oracle answer is only a bounded-error bit, so the $\log$ in $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$ is not needed here; and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q}$.
FIND-1 under a density promise relation \(\Theta(1)\) At most $\mathrm{N}_p = \Theta(1)$ (a noisy quantum algorithm can simulate the classical one), and at least $\mathrm{Q} = \Theta(1)$.
Approximate Hamming weight relation \(\Theta(1)\) At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = \Theta(1)$.
SearchCNF relation \(\Theta(1)\) At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = \Theta(1)$.
Gap-Majority partial \(\widetilde\Theta(\min(n, 1/\delta))\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$.
Gap-Majority at constant gap partial \(\Theta(1)\) Between $\mathrm{Q}$ and $O(\mathrm{Q}\log\mathrm{Q})$.
Parity-labelled FIND-1 partial \(\Theta(1)\) Between $\mathrm{Q} = \Theta(1)$ and $\mathrm{N}_p = \Theta(1)$.
Approximate index partial \(\widetilde O(\sqrt{k\log k})\) $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ with $\mathrm{Q} = O(\sqrt{k\log k})$.
Collision problem partial \(\widetilde\Theta(n^{1/3})\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$.
Element distinctness total \(\widetilde\Theta(n^{2/3})\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$, with $\mathrm{Q} = \Theta(n^{2/3})$. A noisy oracle costs at most a log factor.
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) Robust queries are at least as expensive as exact ones: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(n^{1/3})$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{Q}$: noisy oracles cannot be cheaper than exact ones.
Yamakawa-Zhandry problem relation \(\mathrm{poly}(n)\) At most $\mathrm{Q}\log\mathrm{Q} = \mathrm{poly}(n)$ by generic robustification, at least $\mathrm{Q}$. So even a noisy quantum oracle keeps the exponential advantage.
Surjectivity total \(\tilde\Theta(n)\) Between $\mathrm{Q} = \tilde\Theta(n)$ and the universal ceiling $\mathrm{Q}^{\mathrm{rob}} \le O(n)$ of Buhrman-Newman-Röhrig-de Wolf, who recover all $n$ bits from $O(n)$ noisy queries. Noise is free here because the problem is already maximally hard.
$k$-distinctness total \(\tilde\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n^{3/4-1/(4(2^k-1))})$ by the row above. Even the fourteen-year-old exponent is noise-robust up to a log.
Triangle finding total \(\Omega(m),\ O(m^{5/4}\log m)\) Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so the window is the $\mathrm{Q}$ window plus a log. Noise is not where the difficulty lies.
Recursive Fourier sampling partial \(\Omega(2^{\ell}),\ O(\ell\,2^{\ell})\) Sandwiched by the generic $\mathrm{Q}(f) \le \mathrm{Q}^{\mathrm{rob}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) around $\mathrm{Q} = \Theta(2^{\ell})$ at $g = g_{\mathrm{mod}3}$. Whether the $\ell$ is needed is open: the Bernstein-Vazirani kickback is exact and has no error to amplify, but the recursion must re-run it $\ell$ levels deep.
Welded trees relation \(\Omega(n),\ O(n\log n)\) Squeezed by $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) around $\mathrm{Q} = \Theta(n)$. So the exponential separation from $\mathrm{R}$ survives noisy oracles intact -- unusually, since the quantum walk's advantage is an interference effect.
Local search on the hypercube relation \(\tilde\Theta(2^{n/3})\) Between $\mathrm{Q} = \Theta(2^{n/3}n^{1/6})$ and $O(\mathrm{Q}\log \mathrm{Q}) = O(2^{n/3}n^{7/6})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)).
Local search on the grid relation \(\tilde\Theta(k^{d/3})\ (d \ge 6)\) Between $\mathrm{Q} = \Theta(k^{d/3})$ and $O(\mathrm{Q}\log \mathrm{Q}) = O(k^{d/3}\log k)$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)).
Fourier fishing relation \(\Theta(1)\)· Still constant: $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) reads $O(1)$ at $\mathrm{Q} = 1$, and $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = 1$. So the largest known relational speedup is not an artefact of a noiseless oracle. Medium confidence because the generic simulation is stated asymptotically and the constant-$\mathrm{Q}$ case needs the $O(\mathrm{Q})$ form of it.
Ordered search partial \(\tilde\Theta(\log n)\) Between $\mathrm{Q} = \Theta(\log n)$ and $O(\mathrm{Q}\log \mathrm{Q}) = O(\log n\log\log n)$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)).
Tseitin search on an expander relation \(O(\sqrt n\log n)\) $\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) with $\mathrm{Q}=O(\sqrt n)$.
Inner product mod 2 total \(\Theta(n)\) Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(n)$. Upper: $n$ noisy quantum queries recover all $n$ input bits with high probability [BNRdW05], so no function on $n$ bits costs more. Unlike the classical $\mathrm{N}_p = \Theta(n\log n)$ above, there is no $\log$ -- the same quantum-vs-classical noise gap as for \(\oplus_n\). BNRdW05
Minsky-Papert one-in-a-box total \(\Theta(m^{3/2}) = \Theta(\sqrt N)\)· Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(m^{3/2})$. Upper: the $O(\sqrt N)$ algorithm for a two-level AND-OR tree is robust quantum search [HoyerMoscadeWolf03] -- that is exactly the point of the technique -- so noise costs only a constant factor and no $\log$. HoyerMoscadeWolf03
Sink of a tournament total \(\Omega(\sqrt m),\ O(m\log m)\) Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$, and $\mathrm{Q}$ is itself open here; the upper end also follows from $\mathrm{Q}^{\mathrm{rob}} \le \mathrm{N}_p = O(m\log m)$.
Scorpion graphs total \(\Omega(\sqrt m),\ O(m\log m)\) Lower: $\mathrm{Q} \le \widetilde{\mathrm{Q}}$ and $\mathrm{Q} \ge \widetilde{\deg}/2 = \Omega(\sqrt m)$. Upper: $\widetilde{\mathrm{Q}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$ with $\mathrm{Q} = O(m)$. Inherits the whole $\widetilde{\deg}$-vs-$\deg$ gap of \(\widetilde{\deg}_{\varepsilon}(f)\).
Graph connectivity total \(\Omega(m^{3/2}),\ O(m^{3/2}\log m)\) Generic: $\mathrm{Q}(f) \le \widetilde{\mathrm{Q}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$, with $\mathrm{Q} = \Theta(m^{3/2})$.