Q The Query Complexity Zoo
\(\mathrm{Q}_{0}(f)\)

Zero-error (Las Vegas) quantum query complexity

Quantum algorithm that never errs but may output "don't know" with probability <= 1/2.

Definition

The quantum analogue of $\mathrm{R}_0$: outputs in $\{0,1,\bot\}$, never wrong, $\Pr[\bot]\le 1/2$; cost is the worst-case number of queries. The $\bot$ outcome is what makes a worst-case count meaningful -- as with $\mathrm{R}_0$, an always-answering algorithm with a worst-case bound collapses to $\mathrm{D}$. Charging expected cost instead and never outputting $\bot$ gives the same measure up to a factor of two (Markov in one direction, repetition in the other), and the same conversion applied to a classical Las Vegas algorithm gives $\mathrm{Q}_0(f) \le 2\,\mathrm{R}_0(f)$.

Basic facts

  • $\mathrm{Q}(f) \le \mathrm{Q}_0(f) \le \mathrm{Q}_{\mathrm{E}}(f)$, and $\mathrm{Q}_0(f) \le 2\,\mathrm{R}_0(f)$.
  • The polynomial floor under $\mathrm{Q}_0$ is $\mathrm{rdeg}/2$, not $\deg/2$. Writing $p_b$ for the probability of output $b$ after $T$ queries -- a polynomial of degree $\le 2T$ -- zero error says only that $p_1$ vanishes on $f^{-1}(0)$ and $p_0$ vanishes on $f^{-1}(1)$. So $p_1$ is a nondeterministic polynomial for $f$ and $p_0$ one for $\bar f$, giving $\mathrm{Q}_0(f) \ge \tfrac12\max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\} = \mathrm{rdeg}(f)/2 \ge \mathrm{NQ}(f) - \tfrac12$ -- a zero-error algorithm is in particular a nondeterministic one for $f$ and for $\bar f$. The stronger $\deg(f) \le 2T$ needs $p_1 = f$ exactly, which is $\mathrm{Q}_{\mathrm{E}}$; the difference is real, and it is large -- on \(\bar{\wedge}\text{-tree}\) $\deg = N$ while $\mathrm{rdeg} = \Theta(\sqrt N)$.
  • For total $f$, $\mathrm{Q}_0$ is polynomially related to all the other measures; the exact relations to $\mathrm{Q}_{\mathrm{E}}$ are less studied than the $\mathrm{R}_0$-vs-$\mathrm{R}$ ones.
  • New certification lower bounds: $\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}=\Theta(\mathrm{Q}_0^{\mathrm{cert}})=O(\mathrm{Q}_0)$, $\overline{\deg}^{\mathrm{cert}}=O(\mathrm{Q}_0)$, and $\overline{\mathrm{osdeg}}=O(\mathrm{Q}_0)$ [KLLPV26].
  • AND of complemented EXACT-ONE functions has $\mathrm{Q}_0=\widetilde\Theta(m^{3/2})$ but $\mathrm{Q}=\Theta(m)$ and $\mathrm{rdeg}=m$; bounded degree certification proves the stronger lower bound [KLLPV26, Theorem 10 and Lemma 55].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Q}_{0}(f)\). “\(\mathrm{Q}_{0}(f)\) in terms of it” is the pair with \(\mathrm{Q}_{0}(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}_{0}(f)\) in terms of it It in terms of \(\mathrm{Q}_{0}(f)\)
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total2,4 partial∞ relation∞ derived open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity total1,1 partial1,1 relation1,1 open pair → total1.32,4 partial∞ relation∞ derived open pair →
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity total1,1 partial1,1 relation1,1 open pair → total2,4 partial∞ relation∞ open pair →
\(\mathrm{ndeg}(f)\) Nondeterministic degree total∞ partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity total∞ partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{rdeg}(f)\) Rational degree total2,4 partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) Exact quantum certification complexity total2,4 partial2,? derived open pair → total1,1 partial1,1 derived open pair →
\(\overline{\deg}^{\mathrm{cert}}(f)\) Bounded degree certification complexity total2,4 partial2,? derived open pair → total1,1 partial1,1 derived open pair →
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) One-sided-error bounded polynomial degree total2,4 partial1,? derived open pair → total1,1 partial1,1 open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(n)\) Zero error costs the full $n$: the $\Theta(\sqrt n)$ of Grover is bought entirely with bounded error [BCWZ99]. The polynomial route gives the same thing -- not through $\deg/2$, which is a $\mathrm{Q}_{\mathrm{E}}$ floor, but through $\mathrm{rdeg}/2$: certifying $\mathrm{OR} = 0$ needs the degree-$n$ polynomial $\prod_i(1-x_i)$, so $\mathrm{ndeg}(\bar f) = n$ and $\mathrm{Q}_0 \ge n/2$. BCWZ99
AND total \(\Theta(n)\) Between $\mathrm{rdeg}/2 = n/2$ (here $\mathrm{ndeg}(f) = n$, the monomial $x_1\cdots x_n$) and $\mathrm{D} = n$, exactly as for \(\mathrm{OR}_n\). BCWZ99
PARITY total \(\lceil n/2 \rceil\) Sandwiched between $\mathrm{Q}=\lceil n/2\rceil$ and $\mathrm{Q_E}=\lceil n/2\rceil$. BBCMdW01
MAJORITY total \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Threshold total \(\Theta(n)\) Between $\mathrm{rdeg}(f)/2 = \max\{k,\,n-k+1\}/2 \ge (n+1)/4$ and $\mathrm{Q}_{E}(f) \le n$. (The $\deg/2$ floor would be a $\mathrm{Q}_{\mathrm{E}}$ bound; here $\mathrm{rdeg}$ happens to be $\Theta(n)$ for every $k$, so $\mathrm{Q}_0$ is pinned anyway -- even where $\mathrm{Q} = \Theta(\sqrt{k(n-k+1)})$ is much smaller.)
Symmetric functions (general) total \(\Theta(n)\) Between $\mathrm{rdeg}(f)/2$ and $\mathrm{D}(f)$, both $\Theta(n)$: one of the two sides $\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)$ counts at least half of the $n+1$ levels, since together they count them all. (The $\deg(f) \le 2\mathrm{Q}_0$ used for $\mathrm{Q}_{\mathrm{E}}$ is not available for $\mathrm{Q}_0$; for symmetric $f$ it happens not to matter.) Zero error costs the full $n$ for every symmetric function, however small $\Gamma(f)$ makes the bounded-error value.
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
ODD-MAX-BIT total \(\Theta(n)\) Between $\mathrm{rdeg}/2 = \Theta(n)$ and $\mathrm{D} = n$. Note it is $\mathrm{rdeg}$, not $\deg$, that floors $\mathrm{Q}_0$ -- see \(\mathrm{Q}_{0}(f)\); both are $\Theta(n)$ here.
ADDRESS / multiplexer total \(\Theta(k)\) Between $\mathrm{Q} = \Omega(k)$ and $\mathrm{D} = k+1$.
Binary tree navigation total \(\Theta(k)\) Sandwiched: $\mathrm{Q}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}(f) = \Theta(k)$ and $\mathrm{D}(f) = k$ here.
TRIBES total \(\Omega(n/\log n),\ O(n)\) Not $\Theta(n)$ on the evidence the zoo has: $\deg/2$ floors $\mathrm{Q}_{\mathrm{E}}$, not $\mathrm{Q}_0$, whose floor is $\mathrm{rdeg}/2 = \Theta(n/\log n)$. The same bound comes from a restriction: fixing all but one bit of every tribe to $1$ leaves $\mathrm{OR}_w$ on the free bits, and $\mathrm{Q}_0(\mathrm{OR}_w) = w = \Theta(n/\log n)$ [BCWZ99]. Ceiling $\mathrm{D} = n$. So $\mathrm{Q}_0$ is pinned only to within the $\log n$, still a full quadratic above $\mathrm{Q} = \Theta(\sqrt n)$. BCWZ99
AND-OR tree (depth 2) total \(\Omega(n),\ O(n^2)\) Not pinned at $\Theta(N)$: $\deg/2$ is a floor for $\mathrm{Q}_{\mathrm{E}}$, not for $\mathrm{Q}_0$, whose polynomial floor is $\mathrm{rdeg}/2 = \Theta(n)$ -- the same order as $\mathrm{Q} = \Theta(\sqrt N)$. The ceiling is $\mathrm{D} = n^2$ (equivalently $2\mathrm{R}_0$). So the zoo does not know whether zero error costs the full quadratic here.
NAND tree (balanced AND-OR formula) total \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) The $\deg/2 = N/2$ floor is a $\mathrm{Q}_{\mathrm{E}}$ bound and does not apply here: a zero-error algorithm only forces $p_1$ to vanish on $f^{-1}(0)$, so its polynomial floor is $\mathrm{rdeg}/2 = 2^{\lceil d/2\rceil-1} = \Theta(\sqrt N)$ -- exactly the order of $\mathrm{Q}$. And the ceiling is $\mathrm{Q}_0 \le 2\mathrm{R}_0 = O(N^{0.753\ldots})$, strictly below $\mathrm{D}$: the NAND tree is one of the few places where the Las Vegas ceiling bites before the deterministic one. Contrast $\mathrm{Q}_{\mathrm{E}} = \Theta(N)$, which $\deg$ really does pin.
Recursive MAJORITY-of-3 total \(\Omega(2^d),\ O(2.65^{\,d})\) As on \(\bar{\wedge}\text{-tree}\), $\deg/2$ is a floor for $\mathrm{Q}_{\mathrm{E}}$ and not for $\mathrm{Q}_0$. Lower: $\mathrm{Q} = \Theta(2^d)$, which beats the $\mathrm{rdeg}/2 = \Omega(1.732^{\,d})$ polynomial floor. Upper: $\mathrm{Q}_0 \le 2\mathrm{R}_0 = O(2.64944^{\,d})$, well below $\mathrm{D} = 3^d$.
Kushilevitz's function (iterated) total \(\Omega(\sqrt N),\ O(N)\) The $\deg/2 = 3^k/2$ floor belongs to $\mathrm{Q}_{\mathrm{E}}$ (the row below), not to $\mathrm{Q}_0$: the zero-error floor is $\mathrm{rdeg}/2$, and $\mathrm{rdeg}$ is only bounded above by $3^k$ here. What is left is $\mathrm{Q} = \Omega(\sqrt N)$ underneath and $\mathrm{D} = N$ above.
Rubinstein's function total \(\Omega(\sqrt N),\ O(N)\) Between $\mathrm{Q} = \Theta(\sqrt N)$ and $\mathrm{D} = N$. Not pinned by $\deg$: that floor bounds $\mathrm{Q}_{\mathrm{E}}$, while the $\mathrm{Q}_0$ floor is $\mathrm{rdeg}/2$, and $\mathrm{rdeg}$ is itself unpinned here.
Ambainis-Sun function total \(\Omega(\sqrt N),\ O(N)\) Between $\mathrm{Q} = \Omega(\sqrt N)$ and $\mathrm{D} = \Theta(N)$. The $\deg/2 = \Theta(N)$ floor pins $\mathrm{Q}_{\mathrm{E}}$ but not $\mathrm{Q}_0$, whose floor is $\mathrm{rdeg}/2$ -- and $\mathrm{rdeg}$ has only an upper bound here.
AND composed with NOT-EXACT-HALF total \(\Omega(n^{3/2}),\ O(n^2)\) Between $\mathrm{Q} = \Theta(n^{3/2})$ and $\mathrm{D} = \Theta(n^2)$. The $\deg/2 = \Theta(n^2)$ floor is a $\mathrm{Q}_{\mathrm{E}}$ bound; the $\mathrm{Q}_0$ floor is $\mathrm{rdeg}/2 = \Theta(n)$, weaker than $\mathrm{Q}$ here. So whether forbidding error costs the last $\sqrt n$ is open as far as the zoo knows.
Meiburg's tournament-subcube function total \(\ge 118.3^{\,d}\) putative $\mathrm{Q}_0 \ge \mathrm{Q} \ge 118.3^{\,d}$.
Pointer functions total \(\widetilde O(\sqrt n)\) Variant $g_{m,m}$: squeeze $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E=\widetilde O(\sqrt n)$.
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$, both $\widetilde\Theta(n)$.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{Q}_0\ge\mathrm{Q}$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$.
Gilmer-Saks-Srinivasan functions total \(\Omega(\sqrt n)\) Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6})\) Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$.
Ambainis' exact-quantum function total \(O(2.593^d)\) Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$; the floor is $\Omega(2.1213^d)$.
FORRELATION partial \(O(n)\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = O(n)$.
k-FORRELATION partial \(O(kn)\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = O(kn)$.
Simon's problem partial \(O(2^{n/2})\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = O(2^{n/2})$.
Deutsch-Jozsa partial \(1\) Same: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = 1$.
Bernstein-Vazirani partial \(1\) $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = 1$.
Marked bit partial \(\Omega(\sqrt n),\ O(n)\) Between $\mathrm{Q}$ and $\mathrm{R}_0$. Zero error cannot be cheap -- a zero-error algorithm must actually exhibit a mark -- but no bound better than the sandwich is recorded.
Dense marked bit partial \(\Theta(1)\) $\mathrm{Q}_0 \le 2\,\mathrm{R}_0 = \Theta(1)$ (\(\mathrm{Q}_{0}(f)\)). The contrast with $\mathrm{Q}_E = \Theta(n)$ is the sharpest form of the Las Vegas / exact distinction: both are "never wrong", but only one may say "don't know".
Unstructured search (relation) relation \(n\) putative Same reduction: a zero-error search algorithm decides $\mathrm{OR}$ with zero error, and $\mathrm{Q}_0(\mathrm{OR}_n) = n$. Note the contrast with $\mathrm{R}_0 = \Theta(\mathrm{R})$ for relations -- the randomized zero-error cost collapses to the bounded-error one but the quantum one does not, because the obstruction is the all-zero input, where no witness exists to verify.
FIND-1 under a density promise relation \(\Theta(1)\) The output is self-verifying -- the algorithm only ever names an index it has seen to be $1$ -- so the bounded-error algorithm is already zero-error: $\mathrm{Q}_0 \le \mathrm{R}_0 = O(1)$. Contrast \(\mathrm{SEARCH}_n\), where $\mathrm{Q}_0 = n$ because the all-zero input has no witness; the density promise removes that input.
Approximate Hamming weight relation \(\Theta(n)\)· putative Zero error forces a certificate on every branch, quantumly too: a zero-error algorithm's final state is supported on outcomes valid for every input consistent with what it has learned, and by $\mathrm{C}_{\min} = (1-2\varepsilon)n$ nothing short of that many queries pins an answer down. And $\mathrm{Q}_0 \le \mathrm{R}_0 = \Theta(n)$. So quantum buys nothing at all once error is forbidden -- against $\mathrm{Q} = \Theta(1)$.
SearchCNF relation \(\Theta(1)\) At most $\mathrm{R}_0 = \Theta(1)$; at least $\mathrm{Q}$.
Gap-Majority partial \(\Theta(n)\) putative Zero-error quantum is as expensive as determinism. If a $T$-query algorithm outputs $1$ with probability $p(x) \ge 1/2$ on $1$-inputs and $p(x) = 0$ on $0$-inputs, then $p$ is a non-negative polynomial of degree $\le 2T$, so its symmetrisation $\tilde p(t) = \mathbb{E}_{|x|=t}[p(x)]$ is a genuine univariate polynomial of degree $\le 2T$ vanishing at every integer $t \le n/2-\delta n$ -- that is $(1/2-\delta)n$ distinct roots -- and positive at $t \ge n/2+\delta n$. Hence $\mathrm{Q}_0 \ge (1/4-\delta/2)n$, and $\mathrm{Q}_0 \le \mathrm{R}_0 = \Theta(n)$. Against $\mathrm{Q} = \Theta(\min(n,1/\delta))$ this is an unbounded gap at constant $\delta$.
Gap-Majority at constant gap partial \(\Theta(n)\) putative The polynomial argument of \(\mathrm{GapMaj}^{\delta}_{n}\): a zero-error algorithm's acceptance polynomial symmetrises to a non-negative univariate with $\Theta(n)$ roots. Against $\mathrm{Q} = \Theta(1)$, unbounded.
Parity-labelled FIND-1 partial \(\Theta(1)\) $\mathrm{Q}_0 \le \mathrm{R}_0 = O(1)$; also $\mathrm{Q}_0 \le \mathrm{Q}_E = 1$.
Approximate index partial \(O(\sqrt{k\log k})\) At most $\mathrm{R}_0$; at least $\mathrm{Q}$.
Collision problem partial \(O(n)\) At most $\mathrm{R}_0 = n/2+1$; at least $\mathrm{Q} = \Omega(n^{1/3})$.
Element distinctness total \(\Theta(n)\) A zero-error algorithm is in particular a nondeterministic one for both $f$ and $\bar f$, so $\mathrm{Q}_0 \ge \mathrm{NQ} = \Theta(n)$; and $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} = \Theta(n)$. So the $n^{2/3}$ walk really does need two-sided error: forbidding it costs the full $n^{1/3}$ factor.
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) Between $\mathrm{Q} = \Omega(n^{1/3})$ and $\mathrm{Q}_{\mathrm{E}} = O(n)$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{Q}$.
Yamakawa-Zhandry problem relation \(\mathrm{poly}(n)\) putative Verifiability makes the quantum advantage zero-error: run the $\mathrm{poly}(n)$-query algorithm, spend $n$ more queries checking $H(i,y_i)=1$ for all $i$, and repeat on failure. So $\mathrm{Q}_0 = O(\mathrm{Q} + n) = \mathrm{poly}(n)$ against $\mathrm{R}_0 = 2^{\Omega(n)}$. Contrast \(\mathrm{SEARCH}_n\), where $\mathrm{Q}_0 = n$ because the all-zero input has no witness to verify; here totality is on the quantum side too.
Surjectivity total \(\tilde\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{Q}_{\mathrm{E}}(f)$, both $\tilde\Theta(n)$ here.
$k$-distinctness total \(\Omega\!\big(n^{3/4 - 1/(4(2^k-1))}\big),\ O(n)\) Only the generic $\mathrm{Q}_{\varepsilon} \le \mathrm{Q}_0 \le \mathrm{D}$. Zero error is not obviously free here, unlike on the search problems in this file: a $k$-collision found is a $k$-element certificate, but certifying that no symbol repeats $k$ times costs $\mathrm{C}^0 = n$, so a zero-error algorithm must be right on $0$-inputs with certainty.
Recursive Fourier sampling partial \(\Theta(2^{\ell}) \text{ for } g = g_{\mathrm{mod}3}\) Squeezed to nothing: $\mathrm{Q}_{\varepsilon} \le \mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}}$, and both ends are $\Theta(2^{\ell})$ here -- the exact algorithm already matches the bounded-error lower bound, so error tolerance buys nothing at all on $\mathrm{RFS}$.
Welded trees relation \(\Omega(n),\ O(n^{1.5}\log n)\) Sandwiched between $\mathrm{Q} = \Theta(n)$ and $\mathrm{Q}_{\mathrm{E}} = O(n^{1.5}\log n)$; closing it is the second of the two open questions in the notes below.
Local search on the hypercube relation \(\Theta(2^{n/3}n^{1/6})\) Same verification argument as $\mathrm{R}_0$: a candidate is checked with $\Delta = n$ further queries, so $\mathrm{Q}_0 = O(\mathrm{Q} + n)$, and $n \ll 2^{n/3}$. Zero error is free for every model on this problem, because the answer carries its own certificate.
Local search on the grid relation \(\Theta(k^{d/3})\ (d \ge 6)\) Same verification argument: $\mathrm{Q}_0 = O(\mathrm{Q} + d)$, and $d$ is constant. Zero error is free here for the same reason it is free classically.
Ordered search partial \(\Theta(\log n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{Q}_{\mathrm{E}}(f)$, with both ends $\Theta(\log n)$ here.
Tseitin search on an expander relation \(O(\sqrt n)\) Zero error is free, as it is classically: a candidate vertex is checked with $d = O(1)$ further queries, so $\mathrm{Q}_0 = O(\mathrm{Q} + 1)$, and the $\mathrm{Q}$ row gives $O(\sqrt n)$.
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Minsky-Papert one-in-a-box total \(\Omega(m^2),\ O(m^3)\) putative Lower: planting a $1$ in every box but one restricts $f$ to $\mathrm{OR}_{m^2}$, and zero-error quantum search has no speedup at all, $\mathrm{Q}_0(\mathrm{OR}_b) = b$ [BCWZ99]. Upper: $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} = N$. The gap is genuine -- the zoo does not know whether zero-error costs the full $\Theta(N)$ here, though $\mathrm{Q} = \Theta(N^{1/2})$ shows bounded error does not. BCWZ99
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) putative Zero-error quantum buys nothing here. Fix the tournament on $V\setminus\{v\}$ to be a sink-free one (any cyclic orientation, $m \ge 4$) and leave the $m-1$ edges at $v$ free: the restriction is exactly $\mathrm{AND}_{m-1}$, and zero-error quantum search has no speedup at all, $\mathrm{Q}_0(\mathrm{AND}_{m-1}) = m-1$ [BCWZ99]. Restrictions only decrease $\mathrm{Q}_0$, so $\mathrm{Q}_0 \ge m-1$; and $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} = O(m)$. Note this pins $\mathrm{Q}_0$ even though the bounded-error $\mathrm{Q}$ is open between $\Omega(\sqrt m)$ and $O(m)$.
Scorpion graphs total \(\Theta(m) = \Theta(\sqrt N)\) putative Zero-error quantum buys nothing. Fix the triple $(s,t,b) = (1,2,3)$, make the feet pairwise non-adjacent, fix all touch pairs at their scorpion values except the $m-3$ body-foot pairs, and leave those free: for $m \ge 6$ the result is a scorpion iff all $m-3$ are present (no foot can take over as body, its degree being at most $1$), so the restriction is $\mathrm{AND}_{m-3}$. Zero-error quantum search has no speedup at all, $\mathrm{Q}_0(\mathrm{AND}_k) = k$ [BCWZ99], and restrictions only decrease $\mathrm{Q}_0$, so $\mathrm{Q}_0 \ge m-3$; and $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} = O(m)$. BCWZ99
Graph connectivity total \(\Omega(m^{3/2}),\ O(m^2)\) Between $\mathrm{Q} = \Theta(m^{3/2})$ and $\mathrm{Q}_{\mathrm{E}} = O(m^2)$. Whether zero-error connectivity is as hard as exact connectivity is open as far as the zoo knows; note that the [DHHM06] algorithm is Grover-based and therefore genuinely bounded-error.
Ben-David–Kothari championship function total \(\Theta(n\log n)\) Same discussion; zero-error lower bound from a description-bit restriction. AIK26
Ambainis–Iraids–Kokainis certificate cheat sheet total \(\Theta(n\log^2 n)\) Theorem 2.3. AIK26
AND of complemented EXACT-ONE functions total \(\Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) Theorem 10 and Lemma 55. KLLPV26