Welded Tree 问题

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

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

• 任何经典算法在次指数查询内成功的概率可以忽略——随机焊接和随机顶点标签把”出口方向”彻底藏了起来；
• 一个**连续时间量子行走**只需 $\mathrm{poly}(n)$ 次查询和 $\mathrm{poly}(n)$ 个门就能以高概率找到 EXIT。

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

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,\dots ,C_n$，大小为

$$|C_j|=2^j,0\le j\le n;$$

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

$$|C_j|=2^{2n+1-j},n+1\le j\le 2n+1,$$

其中 $C_{2n+1}=\{\text{EXIT}\}$ 只有一个顶点。焊缝位于中间两列 $C_n$ 与 $C_{n+1}$ 之间。列的分布关于焊缝对称：$1,2,4,\dots ,2^n,2^n,\dots ,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^{\prime }=2n+1-j$ 后化成同一个求和）。因此

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

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

1.3 黑盒（oracle）承诺

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

• 输入一个合法顶点标签，oracle 返回该顶点的（至多 $3$ 个）邻居的标签列表；
• 输入一个不合法的字符串，返回一个特殊值（例如 $\perp$）。

算法一开始只被告知 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,\dots ,2n+1$），定义该列上所有顶点的均匀叠加态

$$|j{⟩}_{\mathrm{col}}=\frac{1}{\sqrt{|C_j|}}\sum _{v\in C_j}|v⟩.$$

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

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

$$|\mathrm{ENTRANCE}⟩=|0{⟩}_{\mathrm{col}}.$$

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

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

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

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

$$A|j{⟩}_{\mathrm{col}}=\frac{1}{\sqrt{|C_j|}}\sum _{v\in C_j}\sum _{u\sim v}|u⟩=\frac{1}{\sqrt{|C_j|}}\sum _u{\mathrm{deg}}_j(u)|u⟩,$$

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

$$A|j{⟩}_{\mathrm{col}}=\frac{1}{\sqrt{|C_j|}}\left(\sum _{u\in C_{j-1}}{\mathrm{deg}}_j(u)|u⟩+\sum _{u\in C_{j+1}}{\mathrm{deg}}_j(u)|u⟩\right).$$

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

• 左树内部（$u\in C_{j+1}$，$j+1\le n$）：$u$ 在 $C_j$ 中恰有 $1$ 个邻居（它的父亲），${\mathrm{deg}}_j(u)=1$；
• 右树内部（$u\in C_{j-1}$，$j-1\ge n+1$）：同理，$u$ 朝 EXIT 方向的父亲唯一，${\mathrm{deg}}_j(u)=1$；
• 焊缝处（$u\in C_{n+1}$，$j=n$）：$u$ 在 $C_n$ 中的邻居就是它的焊缝边端点，环焊接约定下每片叶子恰有 $2$ 条焊缝边，${\mathrm{deg}}_n(u)=2$。

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

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

3.3 列链上的矩阵元

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

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

$$⟨j+1|A|j{⟩}_{\mathrm{col}}=\frac{|E(C_j,C_{j+1})|}{\sqrt{|C_j||C_{j+1}|}}.$$

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

$$⟨j+1|A|j{⟩}_{\mathrm{col}}=\frac{1}{\sqrt{|C_j||C_{j+1}|}}\sum _{v\in C_j}\sum _{u\in C_{j+1}}⟨u|A|v⟩.$$

内层 $⟨u|A|v⟩=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}$，代入：

$$⟨j+1|A|j{⟩}_{\mathrm{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$，代入：

$$⟨j+1|A|j{⟩}_{\mathrm{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$，代入：

$$⟨n+1|A|n{⟩}_{\mathrm{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)⟩$ 按 Schrödinger 方程演化（取 $\hslash =1$）

$$\frac{\mathrm{d}}{\mathrm{d}t}|\psi (t)⟩=-iA|\psi (t)⟩,|\psi (t)⟩=e^{-iAt}|\psi (0)⟩.$$

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

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

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

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

$$|{\varphi }_m⟩=\sqrt{\frac{2}{L+1}}\sum _{j=1}^L\sin (j{k}_m)|j⟩,E_m=2g\cos k_m,k_m=\frac{m\pi }{L+1},m=1,\dots ,L.$$

证明。逐分量验证本征方程。对内部格点 $j$（$2\le j\le L-1$），$H|{\varphi }_m⟩$ 的第 $j$ 个分量正比于

$$g[\sin ((j-1)k_m)+\sin ((j+1)k_m)]=2g\cos k_m\cdot \sin (j{k}_m),$$

这里用了和差化积公式 $\sin (a-b)+\sin (a+b)=2\sin a\cos b$（取 $a=j{k}_m$、$b=k_m$）。右端正是 $E_m$ 乘以 $|{\varphi }_m⟩$ 的第 $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(j{k}_m)=(L+1)/2$ 给出（三角恒等式 ${\sin }^{2}x=\frac{1-\cos 2x}{2}$ 配合等差角余弦求和为零）。Q.E.D.

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

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

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

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

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

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

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

• 对单个本征分量，${\sin }^2$ 型振荡在一个比周期长得多的窗口内取时间平均约为 $1/2$——零点只是测度为零的孤立点，随机时刻几乎必然避开它们；
• 波包在穿越过程中会”扫过”出口列，在长度为 $T$ 的时间窗内，它有 $\Theta (1)$ 比例的时间段里在出口列上保有不可忽略的振幅。

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

$$\mathrm{poly}(n,t,\log (1/ϵ))$$

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

• $n$（顶点标签长度，也是图的”尺寸参数”）：每个标签是约 $2n$ 比特的字符串，对标签做任何算术、比较、受控操作都需要 $O(n)$ 量级的基本门；模拟线路把标签寄存器上的 oracle 调用组织成对 $A$ 的块编码或量子行走步骤，每一步的电路深度随标签长度多项式增长。
• $t$（演化时间）：演化时间越长，需要的模拟步数越多——直观上，要把连续演化切成不随 $t$ 增长而变粗的片段，总代价至少随 $t$ 线性（或近线性）增长。本算法需要 $t\le T=\mathrm{poly}(n)$，所以这个因子也在预算之内。
• $\log (1/ϵ)$（精度）：现代模拟方案（基于线性组合酉、qubitization 或 QSVT）的代价对精度是对数依赖的，这意味着我们可以把 $ϵ$ 取得很小而不显著增加开销。

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

$$\text{总查询数、总门数}=\mathrm{poly}(n)=\mathrm{polylog}(N),$$

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

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

两个保留条款必须讲清楚。第一，上述模拟要求邻居 oracle 可以相干调用：对标签叠加态 ${\sum }_v{\alpha }_v|v⟩$ 的一次查询要返回 ${\sum }_v{\alpha }_v|v⟩|\text{邻居}(v)⟩$，而不是逐个测量后再查。如果邻居 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$：

$$⟨1|A|0{⟩}_{\mathrm{col}}=\frac{2}{\sqrt{1\cdot 2}}=\sqrt{2}.$$

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

$$⟨2|A|1{⟩}_{\mathrm{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$ 个顶点：

$$⟨3|A|2{⟩}_{\mathrm{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{|}_{\mathcal{S}}=\left(\begin{array}{cccccc}0& \sqrt{2}& 0& 0& 0& 0\\ \sqrt{2}& 0& \sqrt{2}& 0& 0& 0\\ 0& \sqrt{2}& 0& 2& 0& 0\\ 0& 0& 2& 0& \sqrt{2}& 0\\ 0& 0& 0& \sqrt{2}& 0& \sqrt{2}\\ 0& 0& 0& 0& \sqrt{2}& 0\end{array}\right),$$

只有中间焊缝那一处的权重是 $2$，其余全是 $\sqrt{2}$。演化 $e^{-iAt}$ 在这个 $6$ 维矩阵的层面上进行，波包从第 $0$ 列传到第 $5$ 列——没有指数大的任何东西出现。读者可以（用习题 5 的方法）亲手对角化这个矩阵，验证若干时刻后第 $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}$ 中的波包以 $\mathrm{poly}(n)$ 时间穿越链条；随机选取演化时刻避开相消干涉的零点，单次测得 EXIT 的概率为逆多项式，重复或振幅放大后高概率成功。
• 实现：度 $3$ 的稀疏性 + 邻居 oracle 提供 sparse access，稀疏 Hamiltonian 模拟以 $\mathrm{poly}(n,t,\log (1/ϵ))$ 资源近似 $e^{-iAt}$，总复杂度 $\mathrm{poly}(n)=\mathrm{polylog}(N)$。

习题

1. （直接计算）验证 Proposition 2 在右树内部的情形：对 $n+1\le j\le 2n$，用 $|C_j|=2^{2n+1-j}$ 与边数 $|E(C_j,C_{j+1})|=|C_j|$ 推出 $⟨j+1|A|j{⟩}_{\mathrm{col}}=\sqrt{2}$。再说明为什么同一条边数公式既能按”$C_j$ 中每个顶点有 $1$ 个父亲”计数、也能按”$C_{j+1}$ 中每个顶点有 $2$ 个孩子”计数，两者为何一致。
2. （不变子空间）补全 Lemma 1 证明中”同一列内 ${\mathrm{deg}}_j(u)$ 为常数”对匹配焊接约定的检查：若焊缝改为一个随机完美匹配（每片叶子恰 $1$ 条焊缝边），焊缝处的矩阵元是多少？列子空间不变性是否仍然成立？
3. （随机性的角色）解释为什么随机焊接的具体排列不改变均匀列态之间的矩阵元：矩阵元只依赖哪几个组合量？如果把列态改成”列内按某种非均匀权重叠加”，不变子空间性质会被哪一步破坏？
4. （随机演化时间）设某列上的振幅形如 $f(t)={\sum }_{m=1}^L{c}_m{e}^{-i{E}_{m}t}$。说明为什么对固定的 $t$ 可能有 $f(t)=0$（相消干涉），而对 $t$ 在足够长区间上取时间平均后 $|f(t){|}^2$ 不可能恒为零。（提示：把 $|f(t){|}^2$ 展开成二重求和，观察哪些项在时间平均下消失。）由此解释”从 $\mathrm{poly}(n)$ 区间随机取 $t$“这一设计避免了什么。
5. （小例子对角化）对第 6 节的 $6\times 6$ 矩阵，利用它关于焊缝的镜像对称性把问题分成对称与反对称两个 $3\times 3$ 块，求出全部本征值（允许数值求解），并粗略估计从 $|0{⟩}_{\mathrm{col}}$ 出发、在 $t\in [0,20]$ 内 $|⟨5|e^{-iAt}|0{⟩}_{\mathrm{col}}{|}^2$ 能达到的量级。这个练习能让你直观看到”波包确实会到出口，但固定时刻可能撞在零点”。
6. （承诺清单）列出这个指数分离所依赖的三个 oracle/分布承诺，并对每一个说明：去掉它之后，经典方或量子方的论证在哪一步失效。

参考文献

• Zoo 编号 26：Andrew Childs、Richard Cleve、Enrico Deotto、Edward Farhi、Sam Gutmann 与 Daniel Spielman, Exponential Algorithmic Speedup by Quantum Walk.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch12-quantum-graphs/welded-tree
• 内容遵循 CC BY-NC-SA 4.0 许可协议