# 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)$ 维的"列子空间"里，指数大的图在这个子空间上退化为一条短链，量子波包沿链传播，多项式时间内就从入口走到出口。本教程按"构造 → 经典下界 → 列子空间 → 量子行走 → 电路实现"的顺序把整条论证讲清楚。

:::{admonition} 本课知识点
:class: tip

1. **[焊接树的构造与顶点计数](#welded-tree-construction)**——能写出各列大小 $|C_j|$ 与顶点总数 $N = 2^{n+2} - 2 = \Theta(2^n)$，验证整图最大度为 $3$，并说明 $\operatorname{poly}(n)$ 与 $\operatorname{polylog}(N)$ 之间的换算。
2. **[邻居 oracle 承诺](#oracle-promise)**——能列出邻居 oracle 的接口规则与两条关键限制，并解释随机标签为何既阻止全局寻址、又隐藏方向信息。
3. **[经典下界的骨架](#classical-lower-bound-welded-tree)**——能解释生日悖论式碰撞计数为何使任何经典算法在 $2^{o(n)}$ 次查询内成功概率可忽略，并指出这条下界依赖的分布承诺与适用范围。
4. **[列态与列子空间的不变性](#column-subspace-invariance)**——能写出列态 $|j\rangle_{\rm col}$、验证其正交归一性，进而补全 Lemma 1 的逐区域检查，说明 $\deg_j(u)$ 在同一列内为常数且与焊接的具体随机排列无关。
5. **[列链上的矩阵元](#chain-matrix-elements)**——能用 Proposition 2 分区域计算树内耦合 $\sqrt{2}$ 与焊缝耦合 $2$，并解释列态归一化为何把列的指数增大抵消成 $\Theta(1)$ 常数。
6. **[链上的波包传播](#wave-propagation)**——能写出均匀链的本征态与本征值（Proposition 3），用群速度上界 $|v| \le 2g$ 说明波包在 $O(n)$ 时间穿越长度 $2n+2$ 的链。
7. **[随机演化时刻与成功概率](#randomized-evolution-time)**——能解释固定时刻测量为何可能撞上相消干涉的零点，并说明随机取 $t$、重复与振幅放大如何把测得 EXIT 的概率提升到接近 $1$。
8. **[稀疏 Hamiltonian 模拟](#sparse-hamiltonian-simulation)**——能说明邻居 oracle 如何提供 sparse-access、代价 $\operatorname{poly}(n, t, \log(1/\epsilon))$ 中各因子的来源，以及相干查询承诺为何是分离结论的一部分。

:::

## 1. 图与黑盒承诺

(welded-tree-construction)=
### 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)}$ 次。两者的差距是指数级的。

(oracle-promise)=
### 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 的路径，等价于在一个指数大的随机迷宫里找唯一出口，而迷宫中每个房间长得都一样。

(classical-lower-bound-welded-tree)=
### 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}.
$$

(column-subspace-invariance)=
### 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$ 维搜索压成二维旋转是同一思想。

(chain-matrix-elements)=
### 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}$。

(wave-propagation)=
### 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)$ 时间尺度内会以不可忽略的概率幅到达出口列。**

(randomized-evolution-time)=
### 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 的保留条款。）

(sparse-hamiltonian-simulation)=
### 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$ 三对角矩阵

$$
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},
$$

只有中间焊缝那一处的权重是 $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 节](#welded-tree-construction)）

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 节](#oracle-promise)）

1. 基础：写出邻居 oracle 对合法标签与非法标签分别返回什么，并说明算法一开始只被告知哪些信息。
2. 进阶：列出这个指数分离所依赖的三个 oracle/分布承诺，并对每一个说明：去掉它之后，经典方或量子方的论证在哪一步失效。

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

**练习 3【经典下界的骨架】**（→ [2.2 节](#classical-lower-bound-welded-tree)）

1. 基础：解释为什么经典算法跨过一条焊缝边之后，"朝 EXIT 方向走"与"往回走"在局部完全对称，而走错一步会进入没有任何地标的指数大子树。
2. 进阶：说明在 $q = 2^{o(n)}$ 次查询内，算法"撞上"自己已探索过的顶点（从而发现环、获得全局线索）的概率大致随什么量缩放；再解释为什么若图以显式邻接表给出，这条下界不再适用。

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

**练习 4【列态与列子空间的不变性】**（→ [3.2 节](#column-subspace-invariance)）

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 节](#chain-matrix-elements)）

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 节](#wave-propagation)）

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 节](#randomized-evolution-time)）

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 节](#sparse-hamiltonian-simulation)）

1. 基础：列出 sparse-access oracle 要求的两个查询能力，并说明邻居 oracle 如何用常数次查询提供它们。
2. 进阶：解释模拟代价 $\operatorname{poly}(n, t, \log(1/\epsilon))$ 中三个因子各自的来源，以及为什么最终总复杂度可以写成 $\operatorname{poly}(n) = \operatorname{polylog}(N)$。
3. 进阶：如果邻居 oracle 只能经典地、一次一个标签地调用，或者"返回邻居"这个动作本身要花 $O(N)$ 时间，量子算法在哪一步失效？为什么说这不是分离结论的缺陷？

## 参考文献

- 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).