# Welded Tree：连续时间量子行走的 Oracle 指数分离

Welded-tree problem 是首批不依赖 Fourier 变换而展示指数算法加速的 oracle 问题。两棵指数大的二叉树在叶层随机焊接；顶点名称随机，算法只知道入口和局部邻居 oracle，目标是找到另一棵树的根。经典局部探索会迷失在随机焊缝，量子连续时间行走却在一个低维对称“列空间”中像穿过路径一样传播。

## 1. 图与黑盒承诺

取两棵深度 $n$ 的完整二叉树：左根为 ENTRANCE，右根为 EXIT。每边有 $2^n$ 个叶子，把左右叶子通过随机交替环或随机匹配结构焊接，使每个内部顶点度 3（根度 2，焊缝点保持常数度）。

所有顶点赋予随机 $2n$ 比特左右的唯一标签。Oracle 输入标签，返回其至多 3 个邻居标签；对非法标签返回特殊值。算法不能从标签看出层数、父子关系或“朝出口方向”。总顶点数

$$
N=\Theta(2^n),
$$

所以 $\operatorname{poly}(n)$ 是 $\operatorname{polylog}(N)$ 时间。

## 2. 为什么经典探索会卡在焊缝

从入口做 DFS/BFS，在前 $n$ 层看到普通二叉树；到达 $2^n$ 个叶子的随机焊缝后，局部邻居没有全局方向。若只访问 $2^{o(n)}$ 个标签，已探索子图以高概率仍像一棵没有显著环结构的随机树，无法判断哪条边最终通向右树根。

随机标签还阻止算法利用预先计算的顶点顺序。经典 lower-bound 论证把自适应查询暴露的局部图与随机生成过程耦合：在次指数查询内碰到足以确定 EXIT 方向的焊缝碰撞概率很小，因此成功率仍可忽略。

这是 oracle/分布承诺下的下界，不表示所有显式给出的两棵树都经典困难。

## 3. 列态把指数图压成一条链

按到入口/出口的层把顶点分成列 $C_0,\ldots,C_{2n+1}$。定义均匀列态

$$
|j\rangle_{\rm col}
=\frac1{\sqrt{|C_j|}}
\sum_{v\in C_j}|v\rangle.
$$

入口态就是 $|0\rangle_{\rm col}$。图邻接矩阵 $A$ 对同列顶点对称，故这些列态张成的不变子空间。相邻列间边数规则使

$$
\langle j+1|A|j\rangle
=\frac{|E(C_j,C_{j+1})|}
{\sqrt{|C_j||C_{j+1}|}}
$$

为常数量级（树内部通常为 $\sqrt2$，焊缝附近为另一个已知常数）。随机焊接的具体排列在均匀求和中消失。

因此 $A$ 在 column subspace 上等价于长度 $O(n)$ 的带权路径邻接矩阵。指数大图的相关动力学被压到 $O(n)$ 维。

## 4. 连续时间行走穿越列链

连续时间量子行走为

$$
U(t)=e^{-iAt}.
$$

从入口开始，列链的本征态近似正弦波；不同本征相位随时间展开，使波包在多项式时间内到达出口列。为避免恰在 destructive-interference 时间测量，算法从一个 $\operatorname{poly}(n)$ 区间随机选择 $t$，模拟 $U(t)$，再测量顶点标签。

单次得到 EXIT 的概率至少逆多项式；重复或振幅放大 $\operatorname{poly}(n)$ 次即高概率成功。总邻居-oracle 查询和门时间均为 $\operatorname{poly}(n)$。

需要注意：测量中间靠近右根的普通顶点不够，因为其随机标签不告诉方向；算法分析直接保证出口根具有可检测概率，或在测得相关区域后继续局部过程。

## 5. 如何实现稀疏 Hamiltonian

$A$ 是最大度 3 的稀疏矩阵。邻居 oracle 可实现 sparse-access oracle：给 $(v,j)$ 返回第 $j$ 个邻居及矩阵元 1。标准 sparse Hamiltonian simulation 在

$$
\operatorname{poly}(n,t,\log(1/\epsilon))
$$

资源内近似 $e^{-iAt}$。由于所需 $t=\operatorname{poly}(n)$，整个行走高效。

如果邻居 oracle 不能相干调用，或返回邻居的代价本身随 $N$ 线性，指数分离不成立。Oracle 能力是算法定义的一部分。

## 6. 小规模直觉

深度 2 时左列大小 $1,2,4$，右侧反向为 $4,2,1$。列态幅度在树展开时被归一化：虽然第三列有 4 个顶点，父层到子层的总耦合不是 4，而是

$$
\frac{8}{\sqrt{2\cdot4}}=2\sqrt2
$$

（具体列/边计数随焊接定义调整）。关键是它保持常数而非指数小，使波可以跨越所有列。

## 7. 意义与边界

- 它证明量子行走自身可产生 oracle 指数加速，不必归约到 HSP。
- 图有特殊全局对称性；任意随机 3-正则图遍历不能直接套用列压缩。
- 经典 lower bound 针对随机标签与随机焊接分布。
- 后续 electric-network/multidimensional walk 框架改善了查询--时间实现，但不改变该例作为 oracle separation 的性质。

## 8. 小结与习题

- 随机标签使经典算法只能局部探索，焊缝隐藏全局方向。
- 入口所在的均匀 column subspace 对邻接矩阵不变。
- 在该子空间中指数图退化为 $O(n)$ 长带权链，连续时间行走可多项式穿越。
- 稀疏 Hamiltonian simulation 把数学行走转成邻居-oracle 电路。

1. 推导一般相邻列耦合的边数公式。
2. 解释随机焊接为何不改变均匀列态间矩阵元。
3. 说明随机演化时间怎样避免固定时刻振幅为零。
4. 列出此指数分离依赖的三个 oracle/分布承诺。

## 参考文献

- Zoo 编号 26：Andrew Childs、Richard Cleve、Enrico Deotto、Edward Farhi、Sam Gutmann 与 Daniel Spielman, [Exponential Algorithmic Speedup by Quantum Walk](https://arxiv.org/abs/quant-ph/0209131).