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

Welded trees

The quantum-walk speedup: $\mathrm{Q} = \Theta(n)$ against $\mathrm{R} = \mathrm{D} = \tilde\Theta(2^{n/2})$ -- exponential in the tree height, but only $\tilde\Theta(\sqrt{N})$ in the vertex count.

relation relational arity: a $9$-edge-coloured adjacency oracle on $2^{2n}$ possible vertex names, for a graph with $2^{n+2}-2$ vertices— also: glued trees, conjoined trees, graph traversal problem

Description

Two complete binary trees of height $n$ are joined leaf-to-leaf by a random cycle alternating between the two leaf sets. Each vertex gets a uniformly random $2n$-bit name, so names are exponentially sparse in the $2^{2n}$ name space, and the oracle maps (name, colour) to the name of the neighbour across the edge of that colour, or to $1^{2n}$ if there is none. Given the name of the ENTRANCE, output the name of the EXIT. The random $9$-colouring is chosen precisely so that it tells a classical algorithm nothing.

This is a relation with a unique valid answer, and the oracle is not a Boolean decision tree: costs below are in oracle calls, and Boolean queries would cost an extra $O(n)$ factor.

Formal definition

$S = \{(\mathcal{O}_{G,\pi,c},\ \pi(\mathrm{EXIT}))\}$ over welded trees $G$ of height $n$, injective namings $\pi: V \hookrightarrow \{0,1\}^{2n}$ with $\pi(\mathrm{ENTRANCE})$ fixed, and proper $9$-edge-colourings $c$.

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(n)\)· putative Upper: [JefferyZur25, §5], a multidimensional (electric-network) quantum walk, $O(n)$ queries and $O(n^2)$ time; [Belovs24welded] reproves it in a page. The 2003 continuous-time walk is not an $O(n)$-query algorithm: simulating $e^{-iHt}$ for $t = O(n^4)$ costs $O(t^2)$ queries, so [CCDFGS03] as stated is $O(n^{8.5})$ queries, brought to $O(n^{2.5}\log^2 n)$ by [AtiaChakraborty21]. Lower, $\Omega(n)$: nobody states this as a theorem, but it is the light-cone argument -- names are random $2n$-bit strings in a space of size $2^{2n}$, so with probability $1 - 2^{-\Omega(n)}$ an algorithm never guesses a name it has not been handed, and after $t$ queries everything it has seen lies within distance $t$ of the ENTRANCE, which is $2n+2$ away from the EXIT; BBBV makes the hybrid argument quantum. [Belovs24welded] calls the linear upper bound optimal, which presupposes it. The $\Theta$ is therefore only as good as that folklore argument, hence the medium confidence. JefferyZur25 Belovs24welded
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(O(n^{1.5}\log n)\) [LiLiLuo24, §5, Alg. 2]: run the plain coined quantum walk for a classically precomputable number of steps, then exact amplitude amplification. Zero error -- one of very few exponential $\mathrm{Q}_E$-vs-$\mathrm{R}$ separations known. Their bounded-error Alg. 1 uses $O(n^2\log n)$ queries. LiLiLuo24
\(\mathrm{D}(f)\) Deterministic query complexity \(\tilde\Theta(2^{n/2})\)· Upper $O(n\,2^{n/2})$: Shalev Ben-David, reported in [AaronsonAmbainis18, fn. 5] as $O(\sqrt N\log N)$ with $N = 2^n$ ($O(\sqrt N \log^2 N)$ with Boolean queries), and written out in full as [Liu17thesis, §4.3, Alg. 5] -- breadth-first search the top $\lceil n/2\rceil$ levels, cross using short probe-trees to tell "up" from "down", then search the last $\lfloor n/2\rfloor$ levels. Lower: $\mathrm{D} \ge \mathrm{R} = \Omega(2^{n/2}/n)$. So randomness buys essentially nothing here: $\mathrm{D}$ and $\mathrm{R}$ agree to within $n^2$. AaronsonAmbainis18 Liu17thesis
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\tilde\Theta(2^{n/2})\)· The window is $[\Omega(2^{n/2}/n),\ O(n\,2^{n/2})]$, so the exponent is pinned and only the polynomial factor is open. Lower: [Liu17thesis, Cor. 25], for the easier task of finding either the EXIT or any cycle; [AaronsonAmbainis18, fn. 5] asserts $\Omega(\sqrt N)$ for constant success probability. Refereed but weaker: $\Omega(2^{n/6})$ [CCDFGS03, Thm. 9] and $\Omega(2^{n/3})$ [FennerZhang03, Thm. 1.2], both in the exponentially-small-success regime. Upper: from $\mathrm{R} \le \mathrm{D}$. Medium confidence: the strong lower bound lives in a thesis and a footnote. Liu17thesis AaronsonAmbainis18
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\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.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(n)\)· $\mathrm{Adv}^{\pm}$ characterises $\mathrm{Q}$ up to constants (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n)$ here. Medium confidence on two counts: the characterisation is proved for state conversion rather than for search relations in general, and the $\Omega(n)$ side of $\mathrm{Q}$ is itself folklore.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\tilde\Theta(2^{n/2})\) Sandwiched: $\mathrm{R}_{\varepsilon} \le \tfrac32\mathrm{R}_0$ and $\mathrm{R}_0 \le \mathrm{D}$, and both ends are $\tilde\Theta(2^{n/2})$. The classical algorithm never gains from being allowed to err: it finds the EXIT by walking to it.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\tilde\Theta(2^{n/2})\) $\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} = \tilde\Theta(2^{n/2})$ here.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\tilde\Theta(2^{n/2})\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \tilde\Theta(2^{n/2})$; the maximising $\mu$ is the uniform distribution over welded trees, namings and colourings, which is exactly what the lower-bound proofs use.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\Theta(4^n)\) putative Adaptivity is not a convenience here, it is the whole problem: $\mathrm{D}^{\mathrm{na}}/\mathrm{D} = \tilde\Theta(2^{3n/2})$. A non-adaptive algorithm must fix its query names in advance knowing only $\pi(\mathrm{ENTRANCE})$, and the $2^{n+2}-2$ real names are a $2^{-n+2}$ fraction of the $2^{2n}$ name space. Upper: query all $9\cdot 2^{2n}$ (name, colour) pairs and reconstruct the graph. Lower: let $S$ be the set of names queried. The transcript reveals $\pi(\mathrm{EXIT})$ only if $\mathrm{EXIT}$ or one of its $\le 3$ neighbours lies in $S$; if not, and if some name outside $S$ is unused, swapping $\pi(\mathrm{EXIT})$ with that name leaves the transcript unchanged and the required output different. So $|S| \ge 2^{2n} - 2^{n+2} - 1$.
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(1)\) putative Nine queries certify the answer, and this is the cleanest statement of what the welded-trees speedup does not give you. Certificate: query $(y,c)$ for all nine colours $c$ at $y = \pi(\mathrm{EXIT})$. The answers show $y$ has exactly two neighbours. In the welded-trees graph only the two roots have degree $2$; every other vertex has degree $3$, and a name that is not a vertex answers $1^{2n}$ nine times. Since $\pi(\mathrm{ENTRANCE})$ is fixed and known and differs from $y$, every legal instance consistent with those nine cells has $\pi(\mathrm{EXIT}) = y$. So $\mathrm{C} \le 9$ while $\mathrm{D} = \tilde\Theta(2^{n/2})$: verifying the exit is free, finding it is not.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(1)\) putative Contrast \(\mathrm{Ts}(G)\), where $\mathrm{cbs} = \Theta(n)$. Every input is critical -- the valid answer $\pi(\mathrm{EXIT})$ is unique -- so the solution function $s$ is forced and $\mathrm{cbs} = \max_x \mathrm{bs}(s,x)$. Let $B$ be a block whose flip changes the answer, and put $y = \pi(\mathrm{EXIT})$. In the modified instance $y$ is not the exit, so $y$ is either a degree-$3$ vertex or not a vertex at all; either way one of the nine cells $(y,c)$ has changed, so $B$ meets $\{(y,c)\}_{c=1}^{9}$. Disjoint blocks therefore number at most nine. At least one exists (rename the exit), so $\mathrm{cbs} = \Theta(1)$ -- which is the witness behind the recorded fact that $\mathrm{D}$ is unbounded in terms of $\mathrm{cbs}$ (\(\mathrm{D}(f)\) vs \(\mathrm{cbs}(S)\)).
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(4^n)\) putative Randomness does not help the non-adaptive algorithm either, so $\mathrm{R}^{\mathrm{na}}/\mathrm{R} = \tilde\Theta(2^{3n/2})$ as well. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = \Theta(4^n)$. Lower: let the algorithm draw a random name set $S$, $|S| = t$. Since $\pi$ is a uniformly random injection with only $\pi(\mathrm{ENTRANCE})$ pinned, the exit and its two neighbours land in $S$ with probability at most $3t/(2^{2n}-1)$; conditioned on missing all three, the transcript is independent of which unqueried unused name carries the exit, and there are $2^{2n} - t - 2^{n+2}$ candidates. So the success probability is at most $3t/(2^{2n}-1) + o(1)$, and $t = \Omega(4^n)$ is needed for $2/3$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\tilde\Theta(2^{n/2})\) Squeezed by $\mathrm{R} \le \mathrm{psD} \le \mathrm{D}$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and here $\mathrm{R}$ and $\mathrm{D}$ already agree to within $n^2$. Pseudo-determinism costs nothing because the answer is unique to begin with: there is only one solution function, so the canonical-answer requirement is vacuous.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\tilde\Theta(2^{n/2})\) At least $\mathrm{R} = \Omega(2^{n/2}/n)$, at most $O(\mathrm{R}\log \mathrm{R}) = O(2^{n/2}n^2)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). Noise costs only a factor $\mathrm{poly}(n)$, which is invisible at this scale.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(n),\ O(n\log n)\) Squeezed by $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) around $\mathrm{Q} = \Theta(n)$. So the exponential separation from $\mathrm{R}$ survives noisy oracles intact -- unusually, since the quantum walk's advantage is an interference effect.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(n)\)· The approximate $\gamma_2$ norm and $\mathrm{Adv}^{\pm}$ agree up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), and $\mathrm{Adv}^{\pm} = \Theta(n)$ here. Medium confidence for the same two reasons as the $\mathrm{Adv}^{\pm}$ row: $\gamma_2$ is only partially defined on relations, and the $\Omega(n)$ side of $\mathrm{Q}$ is folklore.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(n)\)· Between $\mathrm{Adv}^{\pm} = \Theta(n)$ (the multiplicative adversary is at least as strong) and $\mathrm{Q} = \Theta(n)$ (every adversary bound is a lower bound on $\mathrm{Q}$). Same medium-confidence caveats as the $\mathrm{Adv}^{\pm}$ and $\gamma_2$ rows.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(1)\) $1\le\mathrm{C}_{\min}\le\mathrm{C}=\Theta(1)$: nine queries exhibit the EXIT vertex and certify it at every input, so the cheapest input is no cheaper than a constant.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(n)\) $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(n)$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). The positive-weight bound cannot be much smaller than $\mathrm{Q}=\Theta(n)$ here either, but no matching lower bound is recorded: the certificate structure is trivial ($\mathrm{C}=\Theta(1)$), which is exactly the regime where the positive adversary is weak.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\widetilde O(2^{n/2})\) $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10], a bound stated for relations, and $\mathrm{R}=\tilde\Theta(2^{n/2})$. The usual lower bound $\mathrm{prt}\ge\widetilde{\deg}$ is unavailable: approximate degree is not defined for a relation. JainKlauck10
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\widetilde O(2^{n/2})\) $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon=\widetilde O(2^{n/2})$ [JainKlauck10]. JainKlauck10
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\widetilde O(2^{n/2})\) $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon=\widetilde O(2^{n/2})$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting).
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(n)\) Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=\Theta(n)$. Whether it helps at all here is open; the quantum walk already runs in linear time.
\(\mathrm{DTsize}(f)\) Decision tree size \(\Omega(4^n)\) putative Answer counting. Each leaf of a tree is labelled with a single vertex name, and for every one of the $2^{2n}$ names there is a legal instance whose EXIT carries that name, so instances with different EXIT names must reach different leaves. Hence $\mathrm{DTsize}\ge2^{2n}=4^n$ -- the same $\Theta(4^n)$ that makes the non-adaptive complexity trivial.

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. 32 in total, strongest first.

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

Separations it witnesses

Notes

The speedup produces no certificate. [ChildsCoudronGilani23] show that the path-finding version -- output an ENTRANCE-to-EXIT path rather than just the EXIT name -- cannot be solved efficiently by any quantum algorithm that only ever queries names inside a connected subgraph containing the ENTRANCE. The walk necessarily forgets how it got there.

The advantage also lives entirely in the labelled adjacency-list presentation: symmetric graph properties admit at most polynomial quantum speedups (Ben-David, Childs, Gilyen, Kretschmer, Podder, Wang, FOCS 2020).

Open: whether $\mathrm{R} = \Theta(2^{n/2})$ with no $n$ factor (the window is $[\Omega(2^{n/2}/n), O(n2^{n/2})]$), and whether $\mathrm{Q}_E$ can be brought down to $O(n)$.