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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{C}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \tilde\Theta(2^{n/2})\) against \(\mathrm{C}(f) = \Theta(1)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \tilde\Theta(2^{n/2})\) against \(\mathrm{C}_{\min}(f) = \Theta(1)\)
-
\(\mathrm{Q}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{Q}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{cbs}(S) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) = \widetilde\Omega\big(\mathrm{D}(f_n)^{4}\big)\)from \(\mathrm{D}^{\mathrm{na}}(f) = \Theta(4^n)\) against \(\mathrm{D}(f) = \tilde\Theta(2^{n/2})\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) = \widetilde\Omega\big(\mathrm{R}_{\varepsilon}(f_n)^{4}\big)\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(4^n)\) against \(\mathrm{R}_{\varepsilon}(f) = \tilde\Theta(2^{n/2})\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \tilde\Theta(2^{n/2})\) against \(\mathrm{C}_{\min}(f) = \Theta(1)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{C}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \tilde\Theta(2^{n/2})\) against \(\mathrm{C}(f) = \Theta(1)\)
-
\(\mathrm{Q}^{\mathrm{rob}}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{Q}^{\mathrm{rob}}(f) = \Omega(n),\ O(n\log n)\) against \(\mathrm{cbs}(S) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) = \widetilde\Omega\big(\mathrm{psD}(S)(f_n)^{4}\big)\)from \(\mathrm{D}^{\mathrm{na}}(f) = \Theta(4^n)\) against \(\mathrm{psD}(S) = \tilde\Theta(2^{n/2})\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) = \widetilde\Omega\big(\mathrm{D}(f_n)^{4}\big)\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(4^n)\) against \(\mathrm{D}(f) = \tilde\Theta(2^{n/2})\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \tilde\Theta(2^{n/2})\) against \(\mathrm{cbs}(S) = \Theta(1)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{C}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \tilde\Theta(2^{n/2})\) against \(\mathrm{C}(f) = \Theta(1)\)
-
\(\mathrm{R}_{0}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{R}_{0}(f) = \tilde\Theta(2^{n/2})\) against \(\mathrm{C}_{\min}(f) = \Theta(1)\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) = \widetilde\Omega\big(\mathrm{N}_{p}(f_n)^{4}\big)\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(4^n)\) against \(\mathrm{N}_{p}(f) = \tilde\Theta(2^{n/2})\)
… and 18 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Exponential in the tree height: $\mathrm{Q} = \Theta(n)$ against $\mathrm{R} = \tilde\Theta(2^{n/2})$. In the vertex count $N = 2^n$ that reads $\mathrm{Q} = \Theta(\log N)$ vs $\mathrm{R} = \tilde\Theta(\sqrt N)$ -- the same shape as Simon, and not a $2^{\Omega(N)}$ separation.
-
The separation survives at zero error: $\mathrm{Q}_E = O(n^{1.5}\log n)$ against $\mathrm{R} = \tilde\Theta(2^{n/2})$.
-
Not a separation, and that is the point: $\mathrm{D} = O(n2^{n/2})$ while $\mathrm{R} = \Omega(2^{n/2}/n)$, so randomness is worth at most a factor $n^2$ here.
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)$.