\(\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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{C}^1(f) = 1\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = n+1\) against \(\mathrm{C}_{\min}(f) = 1\)
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = n\) against \(\mathrm{rank}(f) = 1\)
-
\(\mathrm{C}(f_n) = \Omega\big(\mathrm{psD}(S)(f_n)\big)\)from \(\mathrm{C}(f) = n\) against \(\mathrm{psD}(S) = \Theta(n)\)
-
\(\mathrm{cbs}(S)(f_n) = \Omega\big(\mathrm{noisyR}(f_n)\big)\)from \(\mathrm{cbs}(S) = n\) against \(\mathrm{noisyR}(f) = \Theta(n)\)
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{C}_{\min}(f) = 1\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = n+1\) against \(\mathrm{C}^1(f) = 1\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\mathrm{C}(f) = n\) against \(\mathrm{rank}(f) = 1\)
-
\(\mathrm{cbs}(S)(f_n) = \Omega\big(\mathrm{noisyR}^{\mathrm{na}}(f_n)\big)\)from \(\mathrm{cbs}(S) = n\) against \(\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(n)\)
-
\(\mathrm{noisyR}(f_n) = \Omega\big(\mathrm{psD}(S)(f_n)\big)\)from \(\mathrm{noisyR}(f) = \Theta(n)\) against \(\mathrm{psD}(S) = \Theta(n)\)
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{rank}(f) = 1\)
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = n\) against \(\mathrm{C}^1(f) = 1\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{C}(f) = n\) against \(\mathrm{C}_{\min}(f) = 1\)
-
\(\mathrm{cbs}(S)(f_n) = \Omega\big(\mathrm{DTsize}(f_n)\big)\)from \(\mathrm{cbs}(S) = n\) against \(\mathrm{DTsize}(f) = n+1\)
… and 54 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{R}=\Theta(\mathrm{Q}^2)$ for a relation, same as the decision version.
-
Quadratic: $\mathrm{Q}_E = n$ against $\mathrm{Q}=\Theta(\sqrt n)$, matching the best possible gap for relations that admit witness verification.