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

在前面的章节里，我们见过的指数级量子加速——Simon 算法、Shor 算法、更一般的隐藏子群问题（HSP）——都有一个共同的技术核心：量子 Fourier 变换。周期、结构、对称性被编码进相位，再由 QFT 把相位翻译成可测量的频率。这自然引出一个问题：不依赖 Fourier 变换，量子计算还能给出指数加速吗？

Welded-tree（焊接树）问题正是对这个问题的第一个肯定回答。Childs、Cleve、Deotto、Farhi、Gutmann 与 Spielman 在 2002 年构造了一个人工图论 oracle 问题：两棵指数大的二叉树在叶层被随机"焊接"在一起，算法从一棵树的根（ENTRANCE）出发，只能通过局部邻居查询探索图，目标是找到另一棵树的根（EXIT）。他们证明了两件事：

  • 任何经典算法在次指数查询内成功的概率可以忽略——随机焊接和随机顶点标签把"出口方向"彻底藏了起来；

  • 一个连续时间量子行走只需 \(\operatorname{poly}(n)\) 次查询和 \(\operatorname{poly}(n)\) 个门就能以高概率找到 EXIT。

这是首个不经过 HSP、不由 Fourier 采样驱动的 oracle 指数分离。它的技术核心完全不同：图的高度对称性使量子态始终被困在一个 \(O(n)\) 维的"列子空间"里，指数大的图在这个子空间上退化为一条短链，量子波包沿链传播，多项式时间内就从入口走到出口。本教程按"构造 → 经典下界 → 列子空间 → 量子行走 → 电路实现"的顺序把整条论证讲清楚。

本课知识点

  1. 焊接树的构造与顶点计数——能写出各列大小 \(|C_j|\) 与顶点总数 \(N = 2^{n+2} - 2 = \Theta(2^n)\)，验证整图最大度为 \(3\)，并说明 \(\operatorname{poly}(n)\) 与 \(\operatorname{polylog}(N)\) 之间的换算。

  2. 邻居 oracle 承诺——能列出邻居 oracle 的接口规则与两条关键限制，并解释随机标签为何既阻止全局寻址、又隐藏方向信息。

  3. 经典下界的骨架——能解释生日悖论式碰撞计数为何使任何经典算法在 \(2^{o(n)}\) 次查询内成功概率可忽略，并指出这条下界依赖的分布承诺与适用范围。

  4. 列态与列子空间的不变性——能写出列态 \(|j\rangle_{\rm col}\)、验证其正交归一性，进而补全 Lemma 1 的逐区域检查，说明 \(\deg_j(u)\) 在同一列内为常数且与焊接的具体随机排列无关。

  5. 列链上的矩阵元——能用 Proposition 2 分区域计算树内耦合 \(\sqrt{2}\) 与焊缝耦合 \(2\)，并解释列态归一化为何把列的指数增大抵消成 \(\Theta(1)\) 常数。

  6. 链上的波包传播——能写出均匀链的本征态与本征值（Proposition 3），用群速度上界 \(|v| \le 2g\) 说明波包在 \(O(n)\) 时间穿越长度 \(2n+2\) 的链。

  7. 随机演化时刻与成功概率——能解释固定时刻测量为何可能撞上相消干涉的零点，并说明随机取 \(t\)、重复与振幅放大如何把测得 EXIT 的概率提升到接近 \(1\)。

  8. 稀疏 Hamiltonian 模拟——能说明邻居 oracle 如何提供 sparse-access、代价 \(\operatorname{poly}(n, t, \log(1/\epsilon))\) 中各因子的来源，以及相干查询承诺为何是分离结论的一部分。

1. 图与黑盒承诺

1.1 焊接树的构造

取两棵深度为 \(n\) 的完整二叉树。左树的根称为 ENTRANCE（入口），右树的根称为 EXIT（出口）。每棵树有 \(n+1\) 层：根所在的第 \(0\) 层有 \(1\) 个顶点，第 \(1\) 层有 \(2\) 个，……，第 \(n\) 层（叶层）有 \(2^n\) 个顶点。

现在把两棵树的叶层"焊"在一起：把左树的 \(2^n\) 个叶子和右树的 \(2^n\) 个叶子排成一个大环，环上左右叶子交替出现，环的循环顺序是随机选取的；环上相邻顶点之间连边。等价地，也可以用两个随机完美匹配来实现焊接。无论哪种约定，焊接的关键性质是：

  • 每个叶子恰好获得常数条（环约定下为 \(2\) 条）跨越左右两树的"焊缝边"；

  • 具体哪条左叶连到哪条右叶是随机的，算法无法预知。

焊接完成后检查度数：根有 \(2\) 个孩子，度为 \(2\)；树内部的非叶顶点有 \(1\) 个父亲和 \(2\) 个孩子，度为 \(3\)；叶子有 \(1\) 个父亲加常数条焊缝边，度也是常数（环约定下为 \(3\)）。所以整张图是最大度为 \(3\) 的稀疏图。

把顶点按"到入口的层距离"排成列：第 \(j\) 列记为 \(C_j\)。左树贡献列 \(C_0, C_1, \ldots, C_n\)，大小为

\[ |C_j| = 2^j, \qquad 0 \le j \le n; \]

右树镜像地贡献列 \(C_{n+1}, \ldots, C_{2n+1}\)，大小为

\[ |C_j| = 2^{2n+1-j}, \qquad n+1 \le j \le 2n+1, \]

其中 \(C_{2n+1} = \{\text{EXIT}\}\) 只有一个顶点。焊缝位于中间两列 \(C_n\) 与 \(C_{n+1}\) 之间。列的分布关于焊缝对称：\(1, 2, 4, \ldots, 2^n, 2^n, \ldots, 4, 2, 1\)。

1.2 顶点计数

总顶点数是两棵树的顶点数之和（焊接只加边、不加顶点）：

\[ N = \sum_{j=0}^{n} 2^j + \sum_{j=n+1}^{2n+1} 2^{2n+1-j} = \left(2^{n+1} - 1\right) + \left(2^{n+1} - 1\right) = 2^{n+2} - 2, \]

其中两个求和都用了等比数列公式 \(\sum_{j=0}^{n} 2^j = 2^{n+1} - 1\)（第二个和号换元 \(j' = 2n+1-j\) 后化成同一个求和）。因此

\[ N = \Theta(2^n). \]

这个关系是整篇教程的复杂度换算基准：关于 \(n\) 的多项式就是关于 \(N\) 的多项式对数。说量子算法用 \(\operatorname{poly}(n)\) 时间，等价于说它对图规模 \(N\) 是 \(\operatorname{polylog}(N)\) 的；说经典算法需要 \(2^{\Omega(n)}\) 次查询，等价于说它需要 \(N^{\Omega(1)}\) 次。两者的差距是指数级的。

1.3 黑盒（oracle）承诺

图的输入方式是这个问题的灵魂。所有顶点被赋予随机生成的、长度约 \(2n\) 比特的唯一标签（标签空间约 \(2^{2n}\) 略大于 \(N\)，足以容纳所有顶点）。算法能访问的唯一接口是邻居 oracle：

  • 输入一个合法顶点标签，oracle 返回该顶点的（至多 \(3\) 个）邻居的标签列表；

  • 输入一个不合法的字符串，返回一个特殊值（例如 \(\bot\)）。

算法一开始只被告知 ENTRANCE 的标签。注意这个输入模型的两条关键限制：

  1. 标签不携带结构信息。标签是随机字符串，从标签本身看不出顶点在第几列、在左树还是右树、哪个邻居更靠近出口。算法对图的全部知识都来自它实际查询过的那些邻接关系。

  2. 不能按标签搜索。标签空间是指数大的，算法无法"猜中"EXIT 的标签，也无法通过枚举标签来定位特定顶点——对一个随机字符串查询，它几乎必然不合法。

也就是说，算法只能做一件事：从已知顶点出发，问邻居、走到邻居、再问邻居，逐步扩展一张局部地图。经典算法的困难与量子算法的机会，都建立在这个承诺之上。

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

2.1 直觉：前半程太容易，后半程没有路标

从 ENTRANCE 出发做 DFS 或 BFS，前 \(n\) 层一切顺利：算法看到的是一棵规规矩矩的二叉树，每问一个顶点就认识它的孩子。但走了 \(n\) 步之后，算法到达叶层——这里有 \(2^n\) 个顶点，焊缝边把它们随机地连到右树的 \(2^n\) 个叶子。

问题出在焊缝边的另一头没有任何方向信息。当算法跨过一条焊缝边到达右树的某个叶子时，它手里只有这个叶子的随机标签；向右树根方向走和向回走，在局部看起来完全对称。右树内部是一棵"上下颠倒"的二叉树：从叶子出发，每个顶点有一个邻居更靠近 EXIT、两个邻居更远离 EXIT，但标签不告诉算法哪个是哪个。一旦走错一步进入某个子树，指数大的子树里没有任何地标能提示"此路不通"。

换句话说：左树把算法汇聚到叶层很容易（顺着孩子走就行），但要从 \(2^n\) 个叶子中找到那条最终连向 EXIT 的路径，等价于在一个指数大的随机迷宫里找唯一出口，而迷宫中每个房间长得都一样。

2.2 下界论证的骨架

严格的经典下界证明（原始论文的核心技术部分）比上面的直觉更细致，其骨架如下。

设想经典算法已经做了 \(q\) 次自适应查询，把已探索的顶点与边画成一张局部子图。把这张局部子图与焊接树的随机生成过程做耦合（coupling）：可以证明，只要 \(q = 2^{o(n)}\)，已探索子图以高概率仍然是一棵（或少数几棵）不含显著环结构的随机树——算法查询到的标签几乎总是"新鲜"的，即对应图中从未探索过的区域。

这个断言的直观原因是生日悖论式的计数：算法最多接触 \(O(q)\) 个标签，而中间地带和右树的规模是 \(2^{\Omega(n)}\) 的。除非算法碰巧"撞上"自己已经探索过的顶点（从而发现焊缝形成的环、获得关于全局结构的线索），它看到的一切与一棵没有出口的无限随机树在统计上无法区分。而发生这种碰撞的概率随 \(q \cdot 2^{-\Omega(n)}\) 缩放，在次指数查询内可以忽略。

随机标签在这里起到双重作用：它既阻止算法预先计算顶点顺序（没有"第 \(i\) 个顶点"这种全局寻址），也保证未探索区域的标签对算法而言与均匀随机无异。由此，任何经典算法在 \(2^{o(n)}\) 次查询内找到 EXIT 的成功概率仍可忽略。

2.3 这条下界的适用范围

必须强调：这是 oracle 模型 + 随机焊接分布下的下界，而不是"任意两棵焊接树都经典困难"。如果图以显式邻接表的形式给出（顶点有规范编号、边列表完整可见），BFS 显然 \(O(N)\) 步就能从 ENTRANCE 走到 EXIT。困难完全来自黑盒承诺：随机标签 + 随机焊接 + 只有局部邻居查询。这个保留条件在第 7 节讨论算法边界时还会回来。

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

经典算法被困住的原因是它只能在顶点层面局部探索。量子算法的第一步是换一个视角：不看单个顶点，而看整列的均匀叠加。本节证明这是合法且代价极小的视角转换——在这个视角下，\(N = \Theta(2^n)\) 个顶点的图退化成一条长度 \(2n+2\) 的链。

3.1 列态的定义

对每一列 \(C_j\)（\(j = 0, 1, \ldots, 2n+1\)），定义该列上所有顶点的均匀叠加态

\[ |j\rangle_{\rm col} = \frac{1}{\sqrt{|C_j|}} \sum_{v \in C_j} |v\rangle. \]

这是一个归一化态：求和共 \(|C_j|\) 项，每项振幅 \(1/\sqrt{|C_j|}\)，模长平方为 \(|C_j| \cdot \frac{1}{|C_j|} = 1\)。不同列的列态互相正交（它们的支集是不相交的顶点集合），所以 \(\{|j\rangle_{\rm col}\}_{j=0}^{2n+1}\) 是 Hilbert 空间中 \(2n+2\) 个正交归一矢量，张成一个 \(2n+2\) 维子空间——称为列子空间（column subspace）。

初态恰好在列子空间里：算法从 ENTRANCE 出发，而 \(C_0 = \{\text{ENTRANCE}\}\) 只有一个顶点，所以

\[ |{\rm ENTRANCE}\rangle = |0\rangle_{\rm col}. \]

3.2 关键引理：列子空间在邻接矩阵下不变

设 \(A\) 为图的邻接矩阵：\(A|v\rangle = \sum_{u \sim v} |u\rangle\)，即把顶点映到它所有邻居的叠加。我们的行走 Hamiltonian 就是 \(A\)（见第 4 节），所以分析演化首先要理解 \(A\) 的作用。

Lemma 1. 列子空间 \(\mathcal{S} = \mathrm{span}\{|j\rangle_{\rm col} : 0 \le j \le 2n+1\}\) 是 \(A\) 的不变子空间。

证明。只需验证每个基矢的像仍在 \(\mathcal{S}\) 中。展开定义并交换求和次序：

\[ A|j\rangle_{\rm col} = \frac{1}{\sqrt{|C_j|}} \sum_{v \in C_j} \sum_{u \sim v} |u\rangle = \frac{1}{\sqrt{|C_j|}} \sum_{u} \deg_j(u)\,|u\rangle, \]

其中 \(\deg_j(u)\) 表示顶点 \(u\) 落在 \(C_j\) 中的邻居个数（交换求和的合法性：所有求和都是有限的）。由于焊接树的每条边都连接相邻两列（列内无边、跨一列以上无边），\(\deg_j(u)\) 只在 \(u \in C_{j-1} \cup C_{j+1}\) 时非零，所以

\[ A|j\rangle_{\rm col} = \frac{1}{\sqrt{|C_j|}} \left( \sum_{u \in C_{j-1}} \deg_j(u)\,|u\rangle + \sum_{u \in C_{j+1}} \deg_j(u)\,|u\rangle \right). \]

右边要成为 \(|j-1\rangle_{\rm col}\) 与 \(|j+1\rangle_{\rm col}\) 的线性组合，充要条件是 \(\deg_j(u)\) 在同一列内不依赖于 \(u\)——即同一列中每个顶点在相邻列里的邻居数相同。逐区域检查焊接树：

  • 左树内部（\(u \in C_{j+1}\)，\(j+1 \le n\)）：\(u\) 在 \(C_j\) 中恰有 \(1\) 个邻居（它的父亲），\(\deg_j(u) = 1\)；

  • 右树内部（\(u \in C_{j-1}\)，\(j-1 \ge n+1\)）：同理，\(u\) 朝 EXIT 方向的父亲唯一，\(\deg_j(u) = 1\)；

  • 焊缝处（\(u \in C_{n+1}\)，\(j = n\)）：\(u\) 在 \(C_n\) 中的邻居就是它的焊缝边端点，环焊接约定下每片叶子恰有 \(2\) 条焊缝边，\(\deg_n(u) = 2\)。

三种情形下 \(\deg_j(u)\) 在同一列内都是常数（注意：焊接的具体随机排列根本不影响这个常数——无论哪片左叶连哪片右叶，每片叶子的焊缝边数都是 \(2\)）。于是两个求和都正比于整列的均匀叠加，\(A|j\rangle_{\rm col} \in \mathcal{S}\)。Q.E.D.

这个引理值得停下来体会。\(A\) 是一个 \(N \times N\) 的矩阵，\(N = \Theta(2^n)\)；但只要我们关心的是从 \(|0\rangle_{\rm col}\) 出发的演化，就永远不需要离开这个 \(2n+2\) 维的子空间。随机焊接的所有"混乱"都被均匀求和平均掉了——这是"对称性降维"的标准戏法，与 Grover 算法中把 \(N\) 维搜索压成二维旋转是同一思想。

3.3 列链上的矩阵元

既然列子空间不变，\(A\) 限制在其上就是一个 \((2n+2) \times (2n+2)\) 的矩阵。又因为边只存在于相邻列之间，这个矩阵是三对角的；邻接矩阵对角元为零（图中无自环），所以非零元只有 \(\langle j+1|A|j\rangle\) 及其对称元。下面把它算出来。

Proposition 2. 记 \(E(C_j, C_{j+1})\) 为两列之间的边集，则

\[ \langle j+1|A|j\rangle_{\rm col} = \frac{|E(C_j, C_{j+1})|}{\sqrt{|C_j|\,|C_{j+1}|}}. \]

证明。由列态定义与 \(A = \sum_{(u,v) \in E} \big(|u\rangle\langle v| + |v\rangle\langle u|\big)\)（每条无向边贡献两个方向的跃迁）：

\[ \langle j+1|A|j\rangle_{\rm col} = \frac{1}{\sqrt{|C_j|\,|C_{j+1}|}} \sum_{v \in C_j} \sum_{u \in C_{j+1}} \langle u|A|v\rangle. \]

内层 \(\langle u|A|v\rangle = 1\) 当且仅当 \((u,v)\) 是一条边，否则为 \(0\)；而跨列边恰好在 \(C_j\) 与 \(C_{j+1}\) 之间，所以双重求和就是在数边数 \(|E(C_j, C_{j+1})|\)。Q.E.D.

现在分区域代入边数：

左树内部（\(0 \le j < n\)）：\(C_j\) 中每个顶点有 \(2\) 个孩子在 \(C_{j+1}\)，故 \(|E(C_j, C_{j+1})| = 2|C_j| = 2^{j+1}\)，代入：

\[ \langle j+1|A|j\rangle_{\rm col} = \frac{2^{j+1}}{\sqrt{2^j \cdot 2^{j+1}}} = \frac{2^{j+1}}{2^j \sqrt{2}} = \sqrt{2}. \]

右树内部（\(n+1 \le j \le 2n\)）：\(C_j\) 中每个顶点朝 EXIT 方向有 \(1\) 个父亲在 \(C_{j+1}\)，故 \(|E| = |C_j| = 2^{2n+1-j}\)，而 \(|C_{j+1}| = 2^{2n-j} = |C_j|/2\)，代入：

\[ \langle j+1|A|j\rangle_{\rm col} = \frac{|C_j|}{\sqrt{|C_j| \cdot |C_j|/2}} = \frac{1}{\sqrt{1/2}} = \sqrt{2}. \]

焊缝（\(j = n\)）：环焊接约定下每片叶子有 \(2\) 条焊缝边，两列各 \(2^n\) 个顶点，故 \(|E(C_n, C_{n+1})| = 2 \cdot 2^n = 2^{n+1}\)，且 \(|C_n| = |C_{n+1}| = 2^n\)，代入：

\[ \langle n+1|A|n\rangle_{\rm col} = \frac{2^{n+1}}{\sqrt{2^n \cdot 2^n}} = \frac{2^{n+1}}{2^n} = 2. \]

三个结果汇总：\(A\) 在列子空间上是长度 \(2n+2\) 的带权路径图的邻接矩阵，链上第 \(j\) 条边的权重在树内部为 \(\sqrt{2}\)、在焊缝处为 \(2\)（匹配焊接约定下焊缝权重是另一个已知常数，例如 \(1\)；具体数值随焊接定义调整，但性质不变）。权重全部是 \(\Theta(1)\) 的常数，没有随 \(n\) 指数衰减或增长。

这就是整个算法的支点：指数大的焊接图，其相关动力学被压缩成一条 \(O(n)\) 长的、边权为常数的链。随机焊接的具体排列在均匀列求和中完全消失——它只通过"每片叶子的焊缝边数"这一个常数进入矩阵元。

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

4.1 从 Hamiltonian 到行走进化算符

连续时间量子行走把图的邻接矩阵直接当作 Hamiltonian：态 \(|\psi(t)\rangle\) 按 Schrödinger 方程演化（取 \(\hbar = 1\)）

\[ \frac{\mathrm{d}}{\mathrm{d}t}|\psi(t)\rangle = -iA|\psi(t)\rangle, \qquad |\psi(t)\rangle = e^{-iAt}|\psi(0)\rangle. \]

这里 \(A\) 是 Hermite 的（实对称），所以 \(U(t) = e^{-iAt}\) 是酉算符，可以原则性地由量子线路实现（实现细节见第 5 节）。由 Lemma 1，初态 \(|0\rangle_{\rm col}\) 的整条演化轨迹都留在列子空间内，我们只需在 \(2n+2\) 维的链上分析 \(e^{-iAt}\)。

4.2 为什么波包一定会走到链的另一端

先做一个理想化：把链上所有边权都近似成同一个常数 \(g\)，即考察 Hamiltonian \(H|j\rangle = g\big(|j-1\rangle + |j+1\rangle\big)\)。这是格点上最标准的"tight-binding"模型，它的本征态和本征值可以完全解出。

Proposition 3. 长度为 \(L\)（格点 \(1, \ldots, L\)）的均匀链，其归一化本征态与本征值为

\[ |\phi_m\rangle = \sqrt{\frac{2}{L+1}} \sum_{j=1}^{L} \sin(jk_m)\,|j\rangle, \qquad E_m = 2g\cos k_m, \qquad k_m = \frac{m\pi}{L+1}, \quad m = 1, \ldots, L. \]

证明。逐分量验证本征方程。对内部格点 \(j\)（\(2 \le j \le L-1\)），\(H|\phi_m\rangle\) 的第 \(j\) 个分量正比于

\[ g\big[\sin((j-1)k_m) + \sin((j+1)k_m)\big] = 2g\cos k_m \cdot \sin(jk_m), \]

这里用了和差化积公式 \(\sin(a-b) + \sin(a+b) = 2\sin a \cos b\)（取 \(a = jk_m\)、\(b = k_m\)）。右端正是 \(E_m\) 乘以 \(|\phi_m\rangle\) 的第 \(j\) 个分量。边界格点 \(j=1\) 与 \(j=L\) 缺少一个邻居，形式上相当于在 \(j=0\) 和 \(j=L+1\) 处补两个振幅恒为零的"虚拟格点"：\(\sin(0 \cdot k_m) = 0\) 自动成立，而 \(\sin((L+1)k_m) = \sin(m\pi) = 0\)——这正是量子化条件 \(k_m = m\pi/(L+1)\) 的来历。归一化因子由 \(\sum_{j=1}^{L}\sin^2(jk_m) = (L+1)/2\) 给出（三角恒等式 \(\sin^2 x = \frac{1-\cos 2x}{2}\) 配合等差角余弦求和为零）。Q.E.D.

这组解的物理图像：本征态是链上的驻波（正弦波包），本征值 \(E_m = 2g\cos k_m\) 是"色散关系"。一个局域在链一端的初态（我们的 \(|0\rangle_{\rm col}\)）是许多本征态的叠加；不同本征态以不同相位速度 \(e^{-iE_m t}\) 演化，叠加图样随时间变化——波包开始沿链移动。波包移动的快慢由群速度决定：

\[ v(k) = \frac{\mathrm{d}E}{\mathrm{d}k} = -2g\sin k, \qquad |v| \le 2g. \]

群速度有常数上界 \(2g\)：这是"链上信息传播速度有限"的严格表述。反过来，它也保证波包不会在链上滞留不动——典型的本征分量带有 \(\Theta(g)\) 的群速度，跨过长度 \(L = 2n+2\) 的链需要的时间是 \(O(L/g) = O(n)\) 量级。

回到真实的焊接树链：边权不是单一常数，而是在 \(\sqrt{2}\)（树内部）与 \(2\)（焊缝）之间变化的已知常数。严格分析需要处理非均匀链的散射（权重突变处波包会部分反射），但所有权重都被常数上下夹住，上述"tight-binding 直觉"仍然成立：波包既不会被焊缝挡住，也不会无限放慢，穿越整条链的时间仍是 \(\operatorname{poly}(n)\)（更精细的分析给出 \(O(n)\) 量级）。原始论文用对链本征结构的精细估计把这一点做成了严格论证；本教程只要求接受这个定性结论：从入口列出发的波包，在 \(\operatorname{poly}(n)\) 时间尺度内会以不可忽略的概率幅到达出口列。

4.3 测量策略：为什么演化时间要随机取

一个自然的想法是：算出波包到达 EXIT 的精确时刻 \(t_*\)，演化 \(U(t_*)\) 后测量。这个做法有一个陷阱。出口列上的振幅是若干振荡项的叠加 \(\sum_m c_m e^{-iE_m t}\)，作为 \(t\) 的函数它会上下振荡，并在某些时刻因**相消干涉（destructive interference）**而恰好为零——如果 \(t_*\) 估计得不准，落在一个零点附近，测量就白费了。

算法的解决办法是用随机性对抗振荡：不取固定时刻，而是从一个 \(\operatorname{poly}(n)\) 长度的区间 \([0, T]\) 中均匀随机地选 \(t\)，模拟 \(U(t)\)，然后测量顶点寄存器。这个策略有效的直觉是：

  • 对单个本征分量，\(\sin^2\) 型振荡在一个比周期长得多的窗口内取时间平均约为 \(1/2\)——零点只是测度为零的孤立点，随机时刻几乎必然避开它们；

  • 波包在穿越过程中会"扫过"出口列，在长度为 \(T\) 的时间窗内，它有 \(\Theta(1)\) 比例的时间段里在出口列上保有不可忽略的振幅。

把两个效应合起来，单次"随机取 \(t\)、演化、测量"在 EXIT 标签上的成功概率至少为 \(1/\operatorname{poly}(n)\)（逆多项式）。接下来是标准收尾：把整个过程独立重复 \(O(1/p) = \operatorname{poly}(n)\) 次，或以振幅放大把重复次数降到 \(O(1/\sqrt{p})\)，即可以高概率测得 EXIT 的标签。由于每次运行的演化时间 \(t \le T = \operatorname{poly}(n)\)，总查询数与门数都是 \(\operatorname{poly}(n)\)。

还有一个细节值得说明（原论文也专门处理过）：有人可能问，波包穿越过程中也会经过靠近 EXIT 的普通顶点，测到它们算不算成功？答案是"不够"——那些顶点同样只有随机标签，算法拿到标签后无法判断它在右树的哪一层、朝哪个方向走。所以分析必须直接保证出口根本身具有可检测的概率（或者，在测得出口附近区域的顶点后，再辅以局部经典过程确认方向）。本教程采用前一种口径。

5. 如何实现稀疏 Hamiltonian

第 4 节把算法写成了 \(e^{-iAt}\)，但邻接矩阵 \(A\) 不是现成的量子门。本节说明：邻居 oracle 恰好提供了模拟这个 Hamiltonian 所需的全部访问能力，且模拟代价是高效的。

5.1 从邻居 oracle 到稀疏矩阵访问

\(A\) 是最大度 \(d = 3\) 的稀疏矩阵：每行至多 \(3\) 个非零元，且非零元全为 \(1\)（无自环、无权重）。稀疏 Hamiltonian 模拟的标准输入模型是 sparse-access oracle，要求两个查询能力：

  1. 定位非零元：给定行 \(v\) 与序号 \(j\)，返回第 \(v\) 行第 \(j\) 个非零元的列位置；

  2. 读取矩阵元：给定 \((v, u)\)，返回 \(A_{vu}\)。

邻居 oracle 几乎原样提供了第 1 条：给顶点标签 \(v\)，它返回至多 \(3\) 个邻居标签，这正是第 \(v\) 行的非零元位置列表。第 2 条随之免费：要判断 \(A_{vu}\) 是否为 \(1\)，查询 \(v\) 的邻居列表看 \(u\) 是否在其中即可，代价是常数次邻居查询。（在相干版本中，这些查询都要以叠加态形式进行，见 5.3 的保留条款。）

5.2 模拟代价逐项分析

稀疏 Hamiltonian 模拟的通用定理（本站 QSP/QSVT 章节介绍过此类结果的门路）给出：对最大度为常数的稀疏 Hermite 矩阵，可以在

\[ \operatorname{poly}\big(n,\ t,\ \log(1/\epsilon)\big) \]

的查询与门复杂度内，把 \(e^{-iAt}\) 近似到算子范数误差 \(\epsilon\)。逐项解释每个因子的来源：

  • \(n\)（顶点标签长度，也是图的"尺寸参数"）：每个标签是约 \(2n\) 比特的字符串，对标签做任何算术、比较、受控操作都需要 \(O(n)\) 量级的基本门；模拟线路把标签寄存器上的 oracle 调用组织成对 \(A\) 的块编码或量子行走步骤，每一步的电路深度随标签长度多项式增长。

  • \(t\)（演化时间）：演化时间越长，需要的模拟步数越多——直观上，要把连续演化切成不随 \(t\) 增长而变粗的片段，总代价至少随 \(t\) 线性（或近线性）增长。本算法需要 \(t \le T = \operatorname{poly}(n)\)，所以这个因子也在预算之内。

  • \(\log(1/\epsilon)\)（精度）：现代模拟方案（基于线性组合酉、qubitization 或 QSVT）的代价对精度是对数依赖的，这意味着我们可以把 \(\epsilon\) 取得很小而不显著增加开销。

最后把第 4 节的重复次数乘进来：单次运行成功概率 \(p \ge 1/\operatorname{poly}(n)\)，重复 \(O(1/p)\) 次（或振幅放大后 \(O(1/\sqrt{p})\) 次），每次模拟误差取 \(\epsilon\) 使 \(O(1/p)\) 次运行的累积误差仍为小常数——由 union bound，取 \(\epsilon = O(p)\) 即可，而 \(\log(1/\epsilon) = O(\log n)\) 被对数因子轻松吸收。于是

\[ \text{总查询数、总门数} = \operatorname{poly}(n) = \operatorname{polylog}(N), \]

与经典下界 \(2^{\Omega(n)}\) 对比，这就是 oracle 意义下的指数分离。

5.3 Oracle 能力是算法定义的一部分

两个保留条款必须讲清楚。第一，上述模拟要求邻居 oracle 可以相干调用：对标签叠加态 \(\sum_v \alpha_v |v\rangle\) 的一次查询要返回 \(\sum_v \alpha_v |v\rangle|\text{邻居}(v)\rangle\)，而不是逐个测量后再查。如果邻居 oracle 只能经典地、一次一个标签地调用，整个量子行走无法实现。

第二，如果"返回邻居"这个动作本身的代价随 \(N\) 线性增长（例如 oracle 内部要扫描整张邻接表），那么每次有效查询就花掉了 \(N^{\Omega(1)}\) 的资源，指数分离同样消失。指数加速的结论是与"常数时间相干邻居查询"这个 oracle 承诺绑定的——这不是缺陷，而是 oracle 分离的标准语义：它分离的是两个计算模型在该输入访问方式下的能力。

6. 小规模直觉：深度 \(n=2\) 手算一遍

抽象公式容易让人不放心，取 \(n = 2\) 把第 3 节的计算完整跑一遍。此时左树列大小为 \(1, 2, 4\)（列 \(C_0, C_1, C_2\)），右树镜像为 \(4, 2, 1\)（列 \(C_3, C_4, C_5\)），共 \(2n+2 = 6\) 列，\(N = 2^{4} - 2 = 14\) 个顶点。

第一跳（\(C_0 \to C_1\)）：ENTRANCE 有 \(2\) 个孩子，\(|E| = 2\)，列大小 \(1\) 与 \(2\)：

\[ \langle 1|A|0\rangle_{\rm col} = \frac{2}{\sqrt{1 \cdot 2}} = \sqrt{2}. \]

第二跳（\(C_1 \to C_2\)）：\(C_1\) 的 \(2\) 个顶点各有 \(2\) 个孩子，\(|E| = 4\)，列大小 \(2\) 与 \(4\)：

\[ \langle 2|A|1\rangle_{\rm col} = \frac{4}{\sqrt{2 \cdot 4}} = \frac{4}{2\sqrt{2}} = \sqrt{2}. \]

这一步值得细看：\(C_2\) 有 \(4\) 个顶点，但父层到子层的总耦合既不是 \(4\)、也不是 \(2\)，而是 \(\sqrt{2}\)。原因是列态的归一化把"顶点变多"的效应反比地压进了振幅里——列越大，均匀叠加摊到每个顶点上的振幅越小，两个效应相消后剩下常数。按焊接定义的不同，这一计数也可能以其他形式出现（例如把焊缝边数按另一约定计入相邻层时，会写出 \(\frac{8}{\sqrt{2 \cdot 4}} = 2\sqrt{2}\) 这样的式子）；具体数值随约定变化，不变的只有一条：耦合保持 \(\Theta(1)\)，绝不随列增大而指数缩小。

焊缝（\(C_2 \to C_3\)）：环焊接下 \(4\) 片左叶各有 \(2\) 条焊缝边，\(|E| = 8\)，两列各 \(4\) 个顶点：

\[ \langle 3|A|2\rangle_{\rm col} = \frac{8}{\sqrt{4 \cdot 4}} = \frac{8}{4} = 2. \]

右树（\(C_3 \to C_4 \to C_5\)）：与左树对称，两跳耦合都是 \(\sqrt{2}\)。于是 \(14 \times 14\) 的邻接矩阵，在列子空间上化成 \(6 \times 6\) 三对角矩阵

\[\begin{split} A\big|_{\mathcal{S}} = \begin{pmatrix} 0 & \sqrt2 & 0 & 0 & 0 & 0\\ \sqrt2 & 0 & \sqrt2 & 0 & 0 & 0\\ 0 & \sqrt2 & 0 & 2 & 0 & 0\\ 0 & 0 & 2 & 0 & \sqrt2 & 0\\ 0 & 0 & 0 & \sqrt2 & 0 & \sqrt2\\ 0 & 0 & 0 & 0 & \sqrt2 & 0 \end{pmatrix}, \end{split}\]

只有中间焊缝那一处的权重是 \(2\)，其余全是 \(\sqrt{2}\)。演化 \(e^{-iAt}\) 在这个 \(6\) 维矩阵的层面上进行，波包从第 \(0\) 列传到第 \(5\) 列——没有指数大的任何东西出现。读者可以（用练习 6 第 2 题的方法）亲手对角化这个矩阵，验证若干时刻后第 \(5\) 列上的概率确实非小。

7. 意义与边界

这个结果在量子算法版图上的位置，可以用几条对比来概括。

  • 它证明量子行走自身就能产生 oracle 指数加速，不必归约到 HSP。 此前的指数加速（Simon、Shor、HSP 家族）全部以 Fourier 采样为引擎；welded-tree 的引擎是图的对称性降维加连续时间传播，是一套完全不同的机制。它打开了"量子行走作为通用算法范式"的方向——后来的离散时间行走搜索、元素区分性等算法都沿此展开。

  • 图的特殊全局对称性是算法的命脉。 列压缩之所以可行，是因为同一列内每个顶点在相邻列中的邻居数相同（Lemma 1 的逐区域检查）。任意随机 \(3\) -正则图没有这个对称性，列压缩不能直接套用；把行走推广到更一般图族需要额外结构。

  • 经典下界针对的是随机标签与随机焊接的分布承诺。 如 2.3 节所述，这不是对显式实例的困难性断言，而是黑盒模型下的分布下界；与 Simon/Shor 的 oracle 分离一样，它说明的是相对化世界中的能力差距。

  • 后续框架改善了实现口径，但不改变分离的性质。 后来的 electric-network 框架与多维量子行走（multidimensional quantum walk）给出了更强的图搜索查询—时间界，其中若干结果可以回看并改进 welded-tree 类问题的查询或时间实现；但这些改进不改变本例作为"量子行走 oracle 指数分离第一例"的历史与概念地位。

8. 本课小结

本教程的论证链条可以压缩成四句话：

  • 承诺：随机标签 + 随机焊接 + 局部邻居 oracle，使经典算法只能做无方向的局部探索，\(2^{o(n)}\) 次查询内看到的仍是随机树，找不到 EXIT。

  • 降维：按层分列、对整列取均匀叠加，得到 \(2n+2\) 维的列子空间；Lemma 1 证明它对邻接矩阵不变，而入口态恰在其中。

  • 传播：列子空间上 \(A\) 是边权 \(\Theta(1)\) 的 \(O(n)\) 长链，连续时间行走 \(e^{-iAt}\) 中的波包以 \(\operatorname{poly}(n)\) 时间穿越链条；随机选取演化时刻避开相消干涉的零点，单次测得 EXIT 的概率为逆多项式，重复或振幅放大后高概率成功。

  • 实现：度 \(3\) 的稀疏性 + 邻居 oracle 提供 sparse access，稀疏 Hamiltonian 模拟以 \(\operatorname{poly}(n, t, \log(1/\epsilon))\) 资源近似 \(e^{-iAt}\)，总复杂度 \(\operatorname{poly}(n) = \operatorname{polylog}(N)\)。

练习题

练习 1【焊接树的构造与顶点计数】（→ 1.1 节）

  1. 基础：取 \(n = 3\)，写出全部 \(2n+2 = 8\) 列的大小、焊缝所连的两列，以及顶点总数 \(N\)。

  2. 进阶：用等比数列求和推导 \(N = 2^{n+2} - 2\)，并解释"量子算法用时 \(\operatorname{poly}(n)\)"与"用时 \(\operatorname{polylog}(N)\)"为什么是同一个说法。

提示：右树的列求和换元 \(j' = 2n+1-j\) 后与左树的求和完全相同。

练习 2【邻居 oracle 承诺】（→ 1.3 节）

  1. 基础：写出邻居 oracle 对合法标签与非法标签分别返回什么，并说明算法一开始只被告知哪些信息。

  2. 进阶：列出这个指数分离所依赖的三个 oracle/分布承诺，并对每一个说明：去掉它之后，经典方或量子方的论证在哪一步失效。

提示：可取随机标签、随机焊接、可相干调用的邻居查询（第三个见 5.3 节）。

练习 3【经典下界的骨架】（→ 2.2 节）

  1. 基础：解释为什么经典算法跨过一条焊缝边之后，"朝 EXIT 方向走"与"往回走"在局部完全对称，而走错一步会进入没有任何地标的指数大子树。

  2. 进阶：说明在 \(q = 2^{o(n)}\) 次查询内，算法"撞上"自己已探索过的顶点（从而发现环、获得全局线索）的概率大致随什么量缩放；再解释为什么若图以显式邻接表给出，这条下界不再适用。

提示：生日悖论式计数——算法至多接触 \(O(q)\) 个标签，而中间地带与右树的规模是 \(2^{\Omega(n)}\)。

练习 4【列态与列子空间的不变性】（→ 3.2 节）

  1. 基础：写出列态 \(|j\rangle_{\rm col}\) 的定义，验证每个列态都归一化、不同列的列态互相正交，并说明初态 \(|{\rm ENTRANCE}\rangle\) 为什么就是 \(|0\rangle_{\rm col}\)。

  2. 进阶：补全 Lemma 1 证明中"同一列内 \(\deg_j(u)\) 为常数"对匹配焊接约定的检查：若焊缝改为一个随机完美匹配（每片叶子恰 \(1\) 条焊缝边），焊缝处的矩阵元是多少？列子空间不变性是否仍然成立？

  3. 进阶：解释为什么随机焊接的具体排列不改变均匀列态之间的矩阵元：矩阵元只依赖哪几个组合量？如果把列态改成"列内按某种非均匀权重叠加"，不变子空间性质会被哪一步破坏？

提示：重新数一数匹配焊接下跨焊缝的边数，再检查 \(\deg_j(u)\) 是否仍逐列为常数。

练习 5【列链上的矩阵元】（→ 3.3 节）

  1. 基础：取 \(n = 2\)，逐跳计算全部 \(5\) 个耦合 \(\langle j+1|A|j\rangle_{\rm col}\)，并写出列子空间上的 \(6 \times 6\) 三对角矩阵。

  2. 进阶：验证 Proposition 2 在右树内部的情形：对 \(n+1 \le j \le 2n\)，用 \(|C_j| = 2^{2n+1-j}\) 与边数 \(|E(C_j, C_{j+1})| = |C_j|\) 推出 \(\langle j+1|A|j\rangle_{\rm col} = \sqrt{2}\)。再说明为什么同一条边数公式既能按"\(C_j\) 中每个顶点有 \(1\) 个父亲"计数、也能按"\(C_{j+1}\) 中每个顶点有 \(2\) 个孩子"计数，两者为何一致。

练习 6【链上的波包传播】（→ 4.2 节）

  1. 基础：对长度 \(L = 3\)、边权 \(g\) 的均匀链，用 Proposition 3 算出全部三个本征值，并写出群速度的常数上界。

  2. 进阶：对第 6 节的 \(6 \times 6\) 矩阵，利用它关于焊缝的镜像对称性把问题分成对称与反对称两个 \(3 \times 3\) 块，求出全部本征值（允许数值求解），并粗略估计从 \(|0\rangle_{\rm col}\) 出发、在 \(t \in [0, 20]\) 内 \(| \langle 5|e^{-iAt}|0\rangle_{\rm col}|^2\) 能达到的量级。这个练习能让你直观看到"波包确实会到出口，但固定时刻可能撞在零点"。

提示：镜像反演 \(|j\rangle \mapsto |5-j\rangle\) 与 \(A\) 对易，本征向量按此反演的 \(\pm 1\) 本征值分成两组，各对应半条链上的问题。

练习 7【随机演化时刻与成功概率】（→ 4.3 节）

  1. 基础：解释"先算出精确到达时刻 \(t_*\)、演化 \(U(t_*)\) 后测量"的策略为什么有陷阱；改为从 \([0, T]\) 均匀随机取 \(t\) 后，单次成功概率与所需重复次数各是什么量级？

  2. 进阶：设某列上的振幅形如 \(f(t) = \sum_{m=1}^{L} c_m e^{-iE_m t}\)。说明为什么对固定的 \(t\) 可能有 \(f(t) = 0\)（相消干涉），而对 \(t\) 在足够长区间上取时间平均后 \(|f(t)|^2\) 不可能恒为零。由此解释"从 \(\operatorname{poly}(n)\) 区间随机取 \(t\)"这一设计避免了什么。

提示：把 \(|f(t)|^2\) 展开成二重求和，观察哪些项在时间平均下消失。

练习 8【稀疏 Hamiltonian 模拟】（→ 5.2 节）

  1. 基础：列出 sparse-access oracle 要求的两个查询能力，并说明邻居 oracle 如何用常数次查询提供它们。

  2. 进阶：解释模拟代价 \(\operatorname{poly}(n, t, \log(1/\epsilon))\) 中三个因子各自的来源，以及为什么最终总复杂度可以写成 \(\operatorname{poly}(n) = \operatorname{polylog}(N)\)。

  3. 进阶：如果邻居 oracle 只能经典地、一次一个标签地调用，或者"返回邻居"这个动作本身要花 \(O(N)\) 时间，量子算法在哪一步失效？为什么说这不是分离结论的缺陷？

参考文献