Q The Query Complexity Zoo
\(\mathrm{LS}(\{0,1\}^n)\)

Local search on the hypercube

The query-complexity home of PLS, and tight in all three models: $\mathrm{D} = \Theta(2^n/\sqrt n)$, $\mathrm{R} = \Theta(2^{n/2}\sqrt n)$, $\mathrm{Q} = \Theta(2^{n/3}n^{1/6})$.

relation relational arity: a table $f:\{0,1\}^n \to \mathbb{Z}$, so $N = 2^n$ integer-valued input cells— also: black-box 2SAT-FLIP

Description

Given $f$ by an oracle, output any $v$ that is a local minimum: $f(v) \le f(w)$ for every neighbour $w$ at Hamming distance $1$. A minimum always exists, so this is a total search problem -- the black-box form of the PLS-complete problem 2SAT-FLIP.

Note the arity convention: there are $N = 2^n$ cells, each holding an integer, so the bounds below are in cell-queries and $n = \log_2 N$.

Formal definition

$S = \{(f, v) : f(v) \le f(w) \text{ for all } w \text{ with } |v \oplus w| = 1\}$.

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(2^n/\sqrt n)\) [LTT89] characterise $\mathrm{D}$ for every graph in terms of vertex cuts; on the cube the optimum is essentially to query the middle layer. Quoted in this form in [SanthaSzegedy09, ยง1]. LTT89 SanthaSzegedy09
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(2^{n/2}\sqrt n)\) Upper: Aldous' generic $O(\sqrt{N\Delta})$ with $N = 2^n$, $\Delta = n$. Lower: [Zhang09localsearch, Thm. 2], after [Aldous83] ($2^{n/2-o(n)}$) and [Aaronson06, Thm. 15] ($\Omega(2^{n/2}/n^2)$). Zhang09localsearch Aldous83
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(2^{n/3}n^{1/6})\) Upper: Aaronson's generic $O(N^{1/3}\Delta^{1/6})$. Lower: [Zhang09localsearch, Thm. 2], after [Aaronson06, Thm. 15] ($\Omega(2^{n/4}/n)$ by the relational adversary) and an unpublished $\Omega(2^{n/3}/n^{O(1)})$ of Ambainis. Zhang09localsearch Aaronson06
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(2^{n/2}\sqrt n)\) A candidate local minimum is verified with $\Delta = n$ further queries, so $\mathrm{R}_0 = O(\mathrm{R} + n)$, and $n \ll \mathrm{R}$ here. Same remark as on \(\mathrm{Find1}_{\ge n/2}\).
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(2^{n/3}n^{1/6})\) $\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(2^{n/3}n^{1/6})$ here.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\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.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(2^{n/2}\sqrt n)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and $\mathrm{R}_{\varepsilon} = \Theta(2^{n/2}\sqrt n)$ here.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(2^{n/2}\sqrt n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(2^{n/2}\sqrt n)$. [Aldous83] and [Zhang09localsearch] both argue against an explicit $\mu$ -- a random-walk / staircase distribution -- so the lower bound is really a $\mathrm{D}^\mu$ bound to begin with.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(2^n\) putative Every cell -- that is, the whole table, $N = 2^n$ -- and the loss against $\mathrm{D} = \Theta(2^n/\sqrt n)$ is only the $\sqrt n$. Suppose the fixed query set $S$ omits the cell $u$ and let $f$ agree on $S$ with the Hamming distance to $u$. If $f(u) = 0$ then $u$ is the unique local minimum, while if $f(u)$ is huge the local minima are exactly the $n$ neighbours of $u$; the transcript is the same in both cases and the required output differs, so $S$ must be everything.
\(\mathrm{C}(f)\) Certificate complexity \(n+1\) putative Exactly $n+1$, at every input. A local minimum $v$ is certified by $f(v)$ together with its $n$ neighbours, and nothing less will do: drop the neighbour $w$ from the certificate and the completion $f(w) = f(v)-1$ is consistent and makes $v$ invalid. So $\mathrm{C} = n+1 = \log_2 N + 1$ against $\mathrm{D} = \Theta(N/\sqrt{\log N})$ -- an exponential $\mathrm{D}$-vs-$\mathrm{C}$ gap on a total search problem, which is the query-complexity content of "PLS solutions are efficiently verifiable".
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(2^n)\) putative Randomness buys nothing without adaptivity, and the gap against $\mathrm{R} = \Theta(2^{n/2}\sqrt n)$ is quadratic. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = 2^n$. Lower: pick $u$ uniformly and let $f$ be the Hamming distance to $u$ except at $u$ itself, where $f(u) \in \{0, 2n\}$ with a fair coin. Both completions are legal, the reading on any cell other than $u$ is identical, and the valid outputs are disjoint -- $\{u\}$ in one case, the $n$ neighbours of $u$ in the other. A fixed query set $S$ of size $t$ contains $u$ with probability $t/2^n$, so the success probability is at most $t/2^n + 1/2$ and $t \ge 2^n/6$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\tilde\Theta(2^{n/2})\) Lower: [Aaronson06, Thm. 15] proves $\Omega(2^{n/2}/n^2)$ by exactly the object this measure names -- his classical relational adversary, a weighting of pairs of inputs with different valid answers. Upper: $\mathrm{CA} \le \mathrm{R} = \Theta(2^{n/2}\sqrt n)$. So the classical adversary is tight here up to $n^{2.5}$, and the sharpening to $\Theta(2^{n/2}\sqrt n)$ in [Zhang09localsearch] came from a different (random-walk) argument rather than from a better relation. Aaronson06 Zhang09localsearch
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Omega(2^{n/2}\sqrt n),\ O(2^n/\sqrt n)\) Only the generic $\mathrm{R} \le \mathrm{psD} \le \mathrm{D}$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and here the two ends are quadratically apart, so this is one of the natural places to look for a genuine pseudo-deterministic separation: a randomized algorithm may return any local minimum, but committing in advance to which one looks much closer to the deterministic problem of finding a canonical minimum.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\tilde\Theta(2^{n/2})\) Between $\mathrm{R} = \Theta(2^{n/2}\sqrt n)$ and $O(\mathrm{R}\log \mathrm{R}) = O(2^{n/2}n^{1.5})$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). The integer cells are read bit by bit under noise, but that only costs $\mathrm{polylog}$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\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)\)).
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(2^{n/3}n^{1/6})\)· Equal to $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), which is $\Theta(2^{n/3}n^{1/6})$ here. Medium confidence only because $\gamma_2$ is listed as partially defined on relations.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(2^{n/3}n^{1/6})\)· Squeezed between $\mathrm{Adv}^{\pm} = \Theta(2^{n/3}n^{1/6})$, which the multiplicative adversary dominates, and $\mathrm{Q} = \Theta(2^{n/3}n^{1/6})$, which every adversary bound is below. Medium confidence for the same definedness reason as $\gamma_2$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(n+1\) Exactly $n+1$, like $\mathrm{C}$: certifying that a vertex is a local minimum means reading it and all $n$ neighbours, and that cost is the same at every input, so the min over inputs equals the max.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(2^{n/3}n^{1/6})\) $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(2^{n/3}n^{1/6})$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). No lower bound is recorded here: the $\Omega(2^{n/3}n^{1/6})$ of [Aaronson06] and [Zhang09localsearch] is a relational adversary argument, which is the \(\mathrm{CA}(f)\) and \(\mathrm{Adv}^{\pm}(f)\) family rather than the positive-weight quantum bound.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Omega(2^{n/3}n^{1/6}),\ O(2^n/\sqrt n)\) $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_{\mathrm{E}}\le\mathrm{D}$, with $\mathrm{Q}=\Theta(2^{n/3}n^{1/6})$ and $\mathrm{D}=\Theta(2^n/\sqrt n)$. Nothing is known about exact local search: even the classical deterministic upper bound is the only ceiling available.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(2^{n/3}n^{1/6})\) Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=\Theta(2^{n/3}n^{1/6})$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(2^{n/2}\sqrt n)\) $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10] in the relation setting, and $\mathrm{R}=\Theta(2^{n/2}\sqrt n)$. The recorded $\mathrm{CA}=\tilde\Theta(2^{n/2})$ does not give a matching lower bound: $\mathrm{CA}\le\mathrm{prt}$ is proved only for partial functions. JainKlauck10
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(2^{n/2}\sqrt n)\) $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10]. JainKlauck10
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(O(2^{n/2}\sqrt n)\) $\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(2^n)\) putative Answer counting: for every vertex $v$ of the cube the table $f(x)=|x\oplus v|$ has $v$ as its unique local minimum, so the $2^n$ vertices force $2^n$ distinct leaves.

Separations it witnesses

Notes

Why the exponents stop there. [SanthaSzegedy09, Thm. 1]: $\mathrm{D}(\mathrm{LS}_G) = O(\mathrm{Q}_{\varepsilon}(\mathrm{LS}_G)^{19})$ for every graph $G$, so local search admits no exponential quantum speedup anywhere. Their route is $\mathrm{D} = O(\log n\,(\Delta + s))$ (Thm. 2) against $\mathrm{Q} = \Omega((s/\Delta)^{1/8}/\log n)$ (Thm. 4), with $s$ the separation number; they say plainly that $19$ is far from optimal, and the true exponent is open.

PLS. 2SAT-FLIP is PLS-complete and its neighbourhood graph is the cube, so the $\Omega(2^{n/3}n^{1/6})$ bound gives an oracle relative to which $\mathsf{PLS} \not\subseteq \mathsf{FBQP}$ [Aaronson06] -- and Santha-Szegedy say that oracle separation can never be made exponential.

Expanders. [BranzeiChooRecker24] get $\mathrm{R} = \Omega(n^{1.5}/g)$ ($g$ the vertex congestion) and $\Omega((s/\Delta)^{1/4})$, giving $\tilde\Theta(\sqrt n)$ on constant-degree expanders; [BranzeiRecker24] get $\mathrm{Q} = \Omega(n^{3/4}/\sqrt g)$.