Q The Query Complexity Zoo
\(\mathrm{LS}([k]^d)\)

Local search on the grid

Tight at $\Theta(k^{d/2})$ randomized for $d\ge4$ and $\Theta(k^{d/3})$ quantum for $d\ge6$; the low dimensions took another decade, and $d=4$ quantum is still open.

relation relational arity: a table $f:[k]^d \to \mathbb{Z}$, so $N = k^d$ cells; $d$ is constant

Description

As \(\mathrm{LS}(\{0,1\}^n)\), on the $d$-dimensional grid with nearest-neighbour edges, so $\Delta = 2d$.

Measure values

MeasureValueNotes
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(k^{d/2})\ (d \ge 4)\) [Zhang09localsearch, Thm. 3], matching Aldous' $O(\sqrt{N\Delta}) = O(k^{d/2})$. The two small dimensions cost a log: $\mathrm{R} = \tilde\Theta(k^{3/2})$ at $d = 3$, from $\Omega((k^3/\log k)^{1/2})$ [Zhang09localsearch, Thm. 3]; and $\mathrm{R} = \tilde\Theta(k)$ at $d = 2$, from $\Omega(k^{1-\delta})$ for every constant $\delta > 0$ [SunYao09] via Sarkozy-Szemeredi, against Aldous' $O(k)$ -- [Zhang09localsearch] had reached only $\Omega(k^{2/3})$ there. Zhang09localsearch Aldous83 SunYao09
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(k^{d/3})\ (d \ge 6)\) [Zhang09localsearch, Thm. 3], matching Aaronson's $O(N^{1/3}\Delta^{1/6}) = O(k^{d/3})$. Below $d = 6$ the picture degrades one dimension at a time: $\tilde\Theta(k^{5/3})$ at $d = 5$, from $\Omega((k^5/\log k)^{1/3})$ [Zhang09localsearch, Thm. 3]; a genuine polynomial gap $\Omega(k^{6/5})$ to $O(k^{4/3})$ at $d = 4$, the one cell of the table still open; $\tilde\Theta(k)$ at $d = 3$, from $\Omega(k^{1-\delta})$ [SunYao09] against $O(k)$; and $\tilde\Theta(\sqrt k)$ at $d = 2$, from $\Omega(k^{1/2-\delta})$ [SunYao09] against $O(\sqrt k\log\log k)$ [Verhoeven06] via graph genus (also $O(\sqrt k(\log\log k)^{1.5})$ [Zhang09localsearch, Thm. 5]). Zhang09localsearch Aaronson06 SunYao09 Verhoeven06
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(k^{d-1})\) Not merely $\tilde\Theta$: the deterministic case was settled before the randomized one. Upper $O(k^{d-1})$ by the divide-and-conquer of Llewellyn-Tovey-Trick: query the $(d-1)$-dimensional middle slab together with the boundary of the current region, take the smallest value seen, and recurse into whichever half contains a strictly smaller neighbour of it -- the region halves each round, so the slab costs form a geometric series. Matching $\Omega(k^{d-1})$ lower bounds are due to [LlewellynTovey93] and, independently, to Althofer and Koschnick (1993). The generic $\mathrm{D} = O(\log N\,(\Delta + s))$ of [SanthaSzegedy09, Thm. 2] with separation number $s([k]^d) = \Theta(k^{d-1})$ recovers the upper bound only up to the $\log$. LTT89 LlewellynTovey93
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(k^{d/2})\ (d \ge 4)\) A candidate local minimum is verified with $\Delta = 2d = O(1)$ further queries, so $\mathrm{R}_0 = O(\mathrm{R} + d)$; with $d$ constant this is $\Theta(k^{d/2})$. Same remark as on \(\mathrm{LS}(\{0,1\}^n)\).
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\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.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(k^{d/2})\ (d \ge 4)\) $\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}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(k^{d/2})\ (d \ge 4)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$; [Zhang09localsearch, Thm. 3] argues against an explicit random-walk distribution, so the bound is a $\mathrm{D}^\mu$ bound already.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(k^{d/3})\ (d \ge 6)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)). In the open dimension $d = 4$ the general adversary inherits the window $[\Omega(k^{6/5}), O(k^{4/3})]$ verbatim.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(k^d = N\) putative Every cell, for every $d \ge 1$, so non-adaptivity is catastrophic already at $d = 2$ where $\mathrm{D} = \Theta(k)$. If the fixed query set $S$ omits the cell $u$, let $f$ agree on $S$ with the $\ell_1$ distance to $u$: when $f(u) = 0$ the unique local minimum is $u$, and when $f(u)$ is huge the local minima are exactly the neighbours of $u$. Same transcript, different required output.
\(\mathrm{C}(f)\) Certificate complexity \(2d+1 = \Theta(1)\) putative A local minimum is certified by its own value and those of its $\le 2d$ neighbours, and no smaller set will do -- omit a neighbour and it can be completed to a strictly smaller value. With $d$ constant this is $\Theta(1)$ against $\mathrm{D} = \Theta(k^{d-1})$, an unbounded $\mathrm{D}$-vs-$\mathrm{C}$ gap on a total search problem. Compare \(\mathrm{LS}(\{0,1\}^n)\), where the same argument gives $n+1$ because the degree grows.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(k^d)\) putative Every cell, even with randomness, so $\mathrm{R}^{\mathrm{na}} = \Theta(\mathrm{D}^{\mathrm{na}}) = \Theta(N)$. Randomise the \(\mathrm{D}^{\mathrm{na}}(f)\) construction: draw $u$ uniformly from $[k]^d$, let $f$ be the $\ell_1$ distance to $u$ off $u$, and set $f(u) \in \{0, 2dk\}$ by a fair coin. The two completions have disjoint solution sets and agree everywhere but $u$, so a fixed query set of size $t$ succeeds with probability at most $t/k^d + 1/2$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Omega(k^{d/2}),\ O(k^{d-1})\ (d \ge 4)\) Only the generic $\mathrm{R} \le \mathrm{psD} \le \mathrm{D}$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). The window is a factor $k^{d/2-1}$ wide, and unlike \(\mathrm{LS}(\{0,1\}^n)\) it stays wide for every fixed $d \ge 4$, so the grid is the cleaner family to ask the pseudo-deterministic question on: is there a canonical local minimum findable in $\tilde O(k^{d/2})$ randomized queries?
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\tilde\Theta(k^{d/2})\ (d \ge 4)\) Between $\mathrm{R} = \Theta(k^{d/2})$ and $O(\mathrm{R}\log \mathrm{R}) = O(k^{d/2}\log k)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\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)\)).
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(k^{d/3})\ (d \ge 6)\)· Equal to $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). Medium confidence only because $\gamma_2$ is listed as partially defined on relations.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(k^{d/3})\ (d \ge 6)\)· Squeezed between $\mathrm{Adv}^{\pm} = \Theta(k^{d/3})$, which it dominates, and $\mathrm{Q} = \Theta(k^{d/3})$, which it is below. Same definedness caveat as $\gamma_2$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(1)\) Between $d+1$ and $\mathrm{C}=2d+1$: a corner cell has only $d$ neighbours to check, an interior cell has $2d$, and $d$ is a constant.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(k^{d/3})\ (d \ge 6)\) $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(k^{d/3})$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). As on \(\mathrm{LS}(\{0,1\}^n)\), the known lower bound is a relational adversary argument rather than a positive-weight quantum one.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Omega(k^{d/3}),\ O(k^{d-1})\ (d \ge 6)\) $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_{\mathrm{E}}\le\mathrm{D}$, with $\mathrm{Q}=\Theta(k^{d/3})$ and $\mathrm{D}=\Theta(k^{d-1})$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(k^{d/3})\ (d \ge 6)\) Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=\Theta(k^{d/3})$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(k^{d/2})\ (d \ge 4)\) $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10] in the relation setting, and $\mathrm{R}=\Theta(k^{d/2})$ for $d\ge4$. JainKlauck10
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(k^{d/2})\ (d \ge 4)\) $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10]. JainKlauck10
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(O(k^{d/2})\ (d \ge 4)\) $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting).
\(\mathrm{DTsize}(f)\) Decision tree size \(\Omega(k^d)\) putative Answer counting: for every cell $v$ the table $f(x)=\|x-v\|_1$ has $v$ as its unique local minimum, so all $N=k^d$ cells force distinct leaves.