Q The Query Complexity Zoo
\(\mathrm{SEARCH}_n\)

Unstructured search (relation)

The canonical relation: output any index $i$ with $x_i=1$.

relation relational arity: $n$ bits

Description

$\mathrm{SEARCH}_n = \{(x,i) : x_i = 1\}$. As stated this is a partial relation (nothing is valid on $x=0^n$); the total version adds $(0^n, \bot)$.

Formal definition

$S = \{(x,i)\in\{0,1\}^n\times[n] : x_i = 1\} \cup \{(0^n,\bot)\}$.

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(\sqrt n)\) Grover96 BBBV97
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\)
\(\mathrm{D}(f)\) Deterministic query complexity \(n\)
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$ and $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_\varepsilon)$, so the multiplicative adversary is $\Theta(\mathrm{Q})$ on every function; here $\mathrm{Q} = \Theta(\sqrt n)$. Spalek08
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(n\) putative An exact algorithm for $\mathrm{SEARCH}$ decides $\mathrm{OR}$ exactly at no extra cost -- output $[\,i \ne \bot\,]$ -- so $\mathrm{Q}_E(\mathrm{SEARCH}) \ge \mathrm{Q}_E(\mathrm{OR}_n) = n$, and $\mathrm{Q}_E \le \mathrm{D} = n$. So the quadratic Grover speedup is entirely a bounded-error effect, even though a search algorithm can always verify its own output: verification makes the error one-sided, not zero.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(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.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) Adaptivity buys nothing: $\mathrm{D} = n$ already, and reading the whole input non-adaptively also costs $n$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) putative Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D} = n$, so the sandwich alone settles it -- no separate pseudo-determinism argument is needed. Contrast \(\mathrm{ApproxHW}\) and \(\mathrm{Find1}_{\ge n/2}\), where $\mathrm{R}$ is small and demanding a canonical answer is what makes the problem hard.
\(\mathrm{DTsize}(f)\) Decision tree size \(n+1\) putative Query $x_1, x_2, \dots$ and stop at the first $1$: $n+1$ leaves. And the all-zero input forces a root-to-leaf path of length $n$, whose $n$ branchings already create $n+1$ leaves.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(n\) putative Exactly $n$, and for every solution function -- so the min over solution functions in the definition of \(\mathrm{cbs}(S)\) does nothing here. The all-zero input is critical: its only valid answer is $\bot$. Flipping any single coordinate $i$ turns it into $e_i$, whose only valid answer is $i \ne \bot$, so all $n$ singletons are sensitive blocks at $0^n$ whatever $s$ is; and $\mathrm{cbs} \le \mathrm{D} = n$. Compare $\mathrm{Q} = \Theta(\sqrt n)$: critical block sensitivity is a classical measure and sees none of the Grover speed-up.
\(\mathrm{C}(f)\) Certificate complexity \(n\) putative Attained only at $0^n$, where the sole valid answer is $\bot$ and certifying it means excluding every index, i.e. reading all $n$ bits. Everywhere else one queried $1$ certifies itself.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(1\) putative One queried $1$ certifies its own index as a valid output. For a search relation this is the whole of the "yes" side; the $n$ in $\mathrm{C}$ comes entirely from the $\bot$ answer.
\(\mathrm{rank}(f)\) Decision tree rank \(1\) putative The tree "query $x_1, x_2, \dots$, stop at the first $1$" is a caterpillar -- every internal node has a leaf child -- so it has rank $1$, and rank $0$ would mean no queries at all. So $\mathrm{rank}=1$ against $\mathrm{D}=n$, exactly as for \(\mathrm{OR}_n\).
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{\varepsilon} = \mathrm{R}_{\varepsilon} = \Theta(n)$.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\) putative Even a product distribution is hard: set each bit to $1$ independently with probability $1/n$. After $q$ all-zero answers each unqueried coordinate is still $1$ with probability $\approx 1/n$, so answering $\bot$ errs with probability $\approx (n-q)/n$ and naming an unqueried index does worse; hence $q = \Omega(n)$. And $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(n)$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(\sqrt n)\) The positive adversary is tight for unstructured search -- it is the original application of the method -- so $\mathrm{Adv} = \Theta(\sqrt n) = \Theta(\mathrm{Q})$. Contrast \(\mathrm{SIMON}_n\) and \(\mathrm{COL}_n\), where the positive adversary collapses to $O(1)$. BBBV97
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\sqrt n)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(\sqrt n)$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(1\) putative At any input with a $1$, that single queried bit certifies its own index. The $n$ in $\mathrm{C}$ comes only from $0^n$, so $\mathrm{C}/\mathrm{C}_{\min} = n$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\)· The relational adversary was designed for exactly this problem and is tight on it: pair $0^n$ with each $e_i$ at weight $1/n$ to get $\Omega(n)$, and $\mathrm{CA} \le \mathrm{R} = \Theta(n)$. Note that $\mathrm{CA}$ lower-bounds $\mathrm{R}$ only, not $\mathrm{Q}$ -- the quantum bound needs \(\mathrm{Adv}(f)\), which stops at $\Theta(\sqrt n)$.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(n)\) At least $\mathrm{R} = \Theta(n)$; and reading each bit $O(1)$ times to beat the noise costs only a constant factor, so $\Theta(n)$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(n)\) From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(n)$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(n)\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon = O(n)$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\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}$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(O(n)\) $\mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon = O(n)$. The usual lower bound $\mathrm{cjdeg} \ge \widetilde{\deg}$ is unavailable: approximate degree is not defined for a relation.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(n\) putative The distinguished answer $\bot$ is valid only at $0^n$, and certifying it means exhibiting a $0$ in every coordinate. So $\mathrm{C}^0 = n$ while $\mathrm{C}^1 = 1$ -- all of $\mathrm{C} = n$ sits on the $\bot$ side.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(n\) putative Parity queries do not help. Along the branch where every answer is $0$, the queried sets $S_1,\dots,S_q$ are fixed; outputting $\bot$ is correct only if $0^n$ is the unique input consistent with those answers, i.e. only if $S_1,\dots,S_q$ span $\mathbb{F}_2^n$, forcing $q \ge n$. And $\mathrm{D}^{\oplus} \le \mathrm{D} = n$. Contrast $\mathrm{D}^{\oplus}(\mathrm{PARITY}) = 1$: what parity queries cannot do is locate a one.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) For a search problem, one-sided error means the algorithm never emits an invalid output, so it must be certain: outputting $\bot$ requires seeing all $n$ zeros. Hence $\mathrm{R}^1 = \Theta(\mathrm{R}_0) = \Theta(n)$, and it is squeezed by $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$ with both ends $\Theta(n)$ anyway.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n)\) putative Upper: $\mathrm{noisyR} \le \mathrm{R} = \Theta(n)$. Lower: $\mathrm{R}$ is linear in the arity, the regime where fractional queries cannot help. Directly: let $\Gamma_i$ be the total squared bias the algorithm spends on coordinate $i$, so the cost is $\sum_i \Gamma_i$. The transcript distributions on $0^n$ and on $e_i$ have KL divergence $O(\Gamma_i)$, so distinguishing $0^n$ from $e_i$ needs $\Gamma_i = \Omega(1)$; this must hold for every $i$, giving cost $\Omega(n)$. CKMPSS23
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity \(\Theta(n)\) Squeezed: $\mathrm{noisyR} = \Theta(n) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(n)$. Theorem 8 of [BenDavidBlais20composition] is unavailable here -- it fails for relations, see \(\mathrm{AGREE}_n\) -- but nothing is lost by committing to the biases in advance at the top of the range.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(1)\)· putative Postselection trivialises search. Prepare $\sum_{i} \alpha_i |i\rangle + \varepsilon|\bot\rangle$ with $\alpha_i = n^{-1/2}$, query $x_i$ into a flag qubit (flag $= x_i$ on the $|i\rangle$ branches, flag $= 1$ on the $|\bot\rangle$ branch), and postselect on flag $= 1$. With $\varepsilon = 1/n$ the surviving state is a uniform superposition over $\{i : x_i = 1\}$ plus a $|\bot\rangle$ component of weight $\varepsilon^2/(\varepsilon^2 + |x|/n) \le 1/n$, so on any $x \ne 0^n$ the measurement returns a valid index, and on $x = 0^n$ only $|\bot\rangle$ survives. One query. Against $\mathrm{R} = \Theta(n)$ and $\mathrm{Q} = \Theta(\sqrt n)$ this is an unbounded gap. MahadevdeWolf15

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 68 in total, strongest first.

… and 54 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses