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/分布承诺。

参考文献