# 邻接表与有界度模型：从 $\sqrt{nm}$ 生成树到 $n^{1/3}$ 性质测试

在[上一课](adjacency-matrix-properties.md)中，图通过邻接矩阵 oracle 给出：一次查询回答一对顶点之间是否有边。这种模型对稠密图是自然，但对稀疏图却有一个根本性的浪费——问一条**不存在的边**也要花掉一次查询，而稀疏图里绝大多数潜在边都不存在。本课研究另一种输入模型：**邻接表（adjacency list，又称 array 模型）**，oracle 直接返回“顶点 $v$ 的第 $i$ 个邻居是谁”。这一改动看似微小，却会从根本上改变多个经典图问题的量子查询复杂度：

- 最小生成树（MST）：从邻接矩阵的 $\Theta(n^{3/2})$ 变为 $\Theta(\sqrt{nm})$，其中 $m$ 是边数；
- 连通性判定：进一步降到 $\Theta(n)$，与输出一棵生成树所需的边数同阶；
- 在更强的**有界度模型**下，若只做**性质测试（property testing）**——区分“图是二分图/扩展图”与“图离二分图/扩展图还很远”——量子查询可以降到 $O(n^{1/3})$（固定度界与距离参数，省略 polylog 与精度因子）。

这些结果分别来自 Dürr、Heiligman、Høyer 与 Mhalla 对图问题查询复杂度的系统研究（Zoo 编号 34），Ambainis、Childs 与 Liu 的有界度图量子性质测试（Zoo 编号 144），以及 Cade、Montanaro 与 Belovs 对时间空间高效实现的后续工作（Zoo 编号 317）。本课的目标是把这三条结论的来龙去脉、核心推导和适用边界讲清楚。

前置知识方面，我们假设读者已掌握本站的 [Grover 算法](../ch03-algo-basics/grover.md)与[振幅放大](../ch03-algo-basics/amplitude-amplification.md)；本课还会以黑箱方式使用两个标准子程序，用到时再简要回顾：

- **量子最小值查找（quantum minimum finding，Dürr–Høyer）**：在 $N$ 个带键值的元素中找最小者，期望 $O(\sqrt{N})$ 次查询；
- **元素互异性（element distinctness）**：判断 $N$ 个元素中是否存在相等的一对，量子查询复杂度 $\Theta(N^{2/3})$（Ambainis 算法，见[碰撞与元素互异性](../ch11-query-complexity/collision-element-distinctness.md)一课）。

先交代经典背景作为对照。经典图算法教科书通常假定图已经完整地放在内存里，关心的是 RAM 模型下的运行时间（例如随机化 MST 可以做到期望 $O(m)$）。但在**查询复杂度**的视角下，图只能通过 oracle 逐条探查，我们关心的是“至少要问 oracle 多少次”。在邻接表模型中，经典算法对 MST、连通性这类问题最坏情形下几乎必须扫描全部 $\Theta(m)$ 个槽位：对手（adversary）可以把那条决定答案的关键边藏在你最后才查的槽位里。量子算法的收益正来自把“逐槽扫描”替换为“对槽位做 Grover 式搜索”——这就是全课反复出现的平方根因子的来源。

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

1. **[邻接表 oracle 与握手引理](#array-oracle-model)**——能写出邻接表 oracle 的查询形式，用握手引理由度序列计算槽位总数与边数，并比较它与邻接矩阵模型互相模拟的代价。
2. **[量子最小值查找](#quantum-minimum-finding)**——能列出 Dürr–Høyer 算法的步骤，解释各次搜索成本为何随阈值排名几何衰减、总计只有期望 $O(\sqrt N)$。
3. **[Cauchy–Schwarz 单轮界与轮次求和](#cauchy-schwarz-round-summation)**——能推导一轮 Borůvka 的成本界 $O(\sqrt{2mc})$，对分量减半的几何级数求和得到 MST 的 $\Theta(\sqrt{nm})$，并指出取等条件。
4. **[连通性的线性复杂度](#connectivity-linear)**——能解释连通性相对 MST 的两点节省与摊还记账论证，说明为何稠密图也能压到 $\Theta(n)$、且 $\Theta(n)$ 不包含枚举全部边。
5. **[性质测试的远/近承诺](#property-testing-promise)**——能写出有界度模型与 $\epsilon$-远的定义，比较精确判定与性质测试两种任务，并解释承诺缺口为何能把复杂度降到精确判定的 $\Omega(\sqrt n)$ 下界之下。
6. **[奇偶碰撞证书与生日界](#parity-collision-birthday)**——能证明二分图的奇偶一致性引理，并由生日界 $K=\Theta(\sqrt n)$ 与元素互异性的 $O(K^{2/3})$ 推出 $O(n^{1/3})$ 的指数来源。
7. **[扩展性测试](#expansion-testing)**——能计算瓶颈图与好扩展图的终点碰撞率并比较数量级差距，解释 $O(n^{1/3})$ 上界与 $\Omega(n^{1/4})$ 下界之间的空隙及固定扩展 gap 的必要性。
8. **[可逆随机游走实现](#reversible-walk-implementation)**——能把一次 $F(s)$ 求值分解为 $L$ 次邻接表查询与可逆清除，说明去随机化游走族如何把空间压到 polylog 量级。

:::

(array-oracle-model)=
## 1. 邻接表（array）oracle 与有界度模型

设无向图 $G=(V,E)$ 有 $n$ 个顶点、$m$ 条边，顶点 $v$ 的度记为 $d_v$。邻接表模型中，每个顶点 $v$ 有一个邻居列表，oracle 接收一个顶点和一个下标

$$
(v,i),\qquad1\le i\le d_v,
$$

返回 $v$ 的第 $i$ 个邻居；对加权图还可以同时返回边权。写成量子 oracle 的标准形式（第三个寄存器是输出寄存器，初态为 $|0\rangle$）：

$$
O_L|v,i,0\rangle
=|v,i,\operatorname{nbr}(v,i)\rangle,
$$

其中 $\operatorname{nbr}(v,i)$ 表示 $v$ 的第 $i$ 个邻居。由于 $\operatorname{nbr}$ 是确定性函数，这个映射是置换，因此可以相干地实现为酉算子，也可以在叠加态上查询——这是把 Grover 搜索套用在邻接槽上的前提。

这个模型有两个结构性事实，后面的所有推导都建立在它们之上。

**事实 1（握手引理）.** 邻接表的总槽位数为

$$
\sum_{v\in V}d_v=2m.
$$

**理由**：每条无向边 $\{u,v\}$ 恰好在 $u$ 的列表里占一个槽、在 $v$ 的列表里占一个槽，所以槽位总数是边数的两倍。这也意味着同一条边会被两个端点各报告一次，算法必须能容忍这种重复（例如把 $\{u,v\}$ 与 $\{v,u\}$ 视为同一候选）。

**事实 2（度信息的获取）.** 要查询第 $i$ 个槽，先得知道 $d_v$ 的范围。通常假定另有一个 **degree oracle** 返回 $d_v$；或者把每个列表补齐到统一长度 $n$，用特殊的“空”标记填充多余位置。两种约定下查询复杂度只差常数因子，但必须在模型声明中说清楚采用哪一种。

作为小例子，考虑 $n=5$、度序列 $(d_1,\dots,d_5)=(3,3,2,1,1)$ 的图：总槽位数 $3+3+2+1+1=10$，故 $m=5$。如果只查询顶点 1 的全部邻居，需要 $3$ 次查询，而不是邻接矩阵模型下的 $4$ 次（询问 $(1,2),(1,3),(1,4),(1,5)$）——稀疏顶点在邻接表下更便宜，这正是两个模型复杂度分叉的起点。

两个模型之间可以互相模拟，但代价不对称，这能帮我们看清各自的能力边界：

- **用邻接表模拟邻接矩阵查询**“$(u,v)$ 是否有边”：需要在 $v$ 的 $d_v$ 个槽中搜索 $u$，量子成本 $O(\sqrt{d_v})$——稀疏时便宜，稠密时一次就要 $O(\sqrt n)$；
- **用邻接矩阵模拟邻接表查询**“$v$ 的第 $i$ 个邻居是谁”：需要在 $v$ 对应的整行（$n$ 个 entry）中找出第 $i$ 个 $1$，等价于在 $n$ 个元素中找第 $i$ 个标记，最坏 $\Theta(\sqrt n)$ 量子查询。

因此“邻接表模型更强”并不是免费的等价交换：它让“枚举邻居”变便宜，却让“确认一条特定的非边”失去了直接入口。选择哪个模型取决于问题本身更依赖哪种操作——MST、连通性依赖枚举出边，适合邻接表；而像三角形查找那样频繁确认任意顶点对之间是否有边的问题，邻接矩阵往往更顺手。

**有界度模型（bounded-degree model）** 是性质测试部分的标准输入模型：承诺所有顶点的度不超过常数 $d$，即 $d_v\le d=O(1)$。此时输入总规模为 $O(dn)=O(n)$，可以把它想成一个有 $dn$ 个槽的数组。在这个模型里，两个图的**距离**按槽位定义：把图 $G$ 改成图 $G'$ 最少需要修改多少个邻接槽。称图 $G$ 离某个性质 $\mathcal{P}$ 是 **$\epsilon$-远（$\epsilon$-far）** 的，如果任何满足 $\mathcal{P}$ 的图都与 $G$ 相差至少 $\epsilon dn$ 个槽。换句话说，“$\epsilon$-远”不是“差一点就满足”，而是“必须动掉输入的一个常数比例才能满足”。第 7 节会用一个奇环的具体计算把这个定义落到实处。

## 2. Borůvka 框架与 $\sqrt{nm}$ 的 MST 分析

本节证明 array 模型下 MST 的量子查询复杂度是 $O(\sqrt{nm})$；第 2.4 小节再说明它有匹配的下界，因此实际上是 $\Theta(\sqrt{nm})$。

### 2.1 经典 Borůvka 算法回顾

Borůvka 算法（1926 年，历史上最早的 MST 算法之一）维护一个**生成森林**：初始时每个顶点自成一个连通分量，然后反复执行如下一轮（phase）：

1. 对每个当前分量 $C$，找出一条离开 $C$ 的**最轻边**（一端在 $C$ 内、一端在 $C$ 外的边中权最小者）；
2. 把所有这些边加入森林，沿它们合并分量。

两条标准的正确性事实：其一，任意分量的最轻出边必然属于某棵 MST（割性质，cut property）；其二，每一轮结束后分量数至少减半——因为每个分量都伸出至少一条边（在图的每个连通块内部），合并后每个新分量至少包含两个旧分量。因此总轮数不超过 $\lceil\log_2 n\rceil$。

经典的逐槽扫描在每一轮要看完所有槽位，总计 $O(m\log n)$ 次查询。量子化改造只动第一步：把“找最轻出边”换成量子最小值查找。

(quantum-minimum-finding)=
### 2.2 量子最小值查找

**量子最小值查找（Dürr–Høyer）** 是这样工作的：给定 $N$ 个元素，每个元素有一个可通过 oracle 查询的键值，算法以期望 $O(\sqrt{N})$ 次查询输出最小元素。步骤如下：

1. 均匀随机取一个初始元素，把它的键值作为当前阈值；
2. 对“键值严格小于阈值”的元素做 **Grover 搜索**——用 BBHT 的未知命中数版本，在 $N$ 个元素中有 $M$ 个命中时，期望 $O(\sqrt{N/M})$ 次查询就能找到一个命中；
3. 每找到一个更小的元素就把它设为新阈值，回到第 2 步；直到搜索空手而归，当前阈值即最小值。

为什么总成本不是“$O(\log N)$ 次搜索 $\times$ 每次 $\sqrt N$”？关键是把各次搜索的成本与阈值的**排名**挂钩。设某次搜索前当前阈值在所有元素中排第 $r$（即有 $r$ 个元素比它小），则该次搜索的命中数 $M=r$，成本为 $O(\sqrt{N/r})$。而搜到的元素在这 $r$ 个更优元素中是均匀随机的，因此新阈值的期望排名约为 $r/2$——排名按几何速度下降。设各次阈值的排名为 $r_0>r_1>\cdots$，其中 $r_k\approx r_0/2^k$，总成本的期望为

$$
\sum_k O\!\left(\sqrt{\frac{N}{r_k}}\right)
=\sqrt{\frac{N}{r_0}}\sum_k 2^{k/2}.
$$

这是公比 $\sqrt2>1$ 的几何级数，由它的**最后一项**主导（排名触底 $r=O(1)$ 时项为 $\sqrt N$），所以整个求和是 $O(\sqrt N)$ 而非 $O(\sqrt N\log N)$。严格的期望分析见 Dürr–Høyer 原文；在本课我们只使用它的接口：**搜索空间是 $N$ 个槽，找最小者的成本是 $O(\sqrt{N})$。** 通过与振幅放大相同的标准重复技巧，成功概率可以从常数提升到 $1-\delta$，代价是 $O(\log\frac1\delta)$ 的乘性因子。

(cauchy-schwarz-round-summation)=
### 2.3 单轮成本的 Cauchy–Schwarz 求和

对当前分量 $C$，定义它的**槽位总数**

$$
D(C)=\sum_{v\in C}d_v.
$$

分量 $C$ 的所有候选出边都藏在它的 $D(C)$ 个邻接槽里：遍历 $C$ 中每个顶点的邻居列表，把“邻居不在 $C$ 内”的槽挑出来比较边权即可。因此，在这 $D(C)$ 个槽上运行量子最小值查找，成本为

$$
O(\sqrt{D(C)}).
$$

注意这里搜索空间的大小是 $D(C)$ 而不是 $m$：分量越小，为它找边越便宜。这是邻接表模型相对于邻接矩阵模型的关键优势——邻接矩阵模型里候选边数是 $|C|(n-|C|)\approx n|C|$，与分量的真实邻接规模无关。

设当前一轮有 $c$ 个分量 $C_1,\dots,C_c$。它们构成顶点集的一个划分，因此由握手引理（事实 1），

$$
\sum_{j=1}^{c}D(C_j)=\sum_{j=1}^{c}\sum_{v\in C_j}d_v=\sum_{v\in V}d_v=2m,
$$

其中第一个等号是 $D$ 的定义，第二个等号利用了“不重不漏”：每个顶点恰好属于一个分量。

**定理（单轮成本）.** 一轮 Borůvka 的总查询成本为

$$
\sum_{j=1}^{c}O(\sqrt{D(C_j)})=O(\sqrt{2mc}).
$$

**证明.** 只需处理求和部分。对实向量 $a=(\sqrt{D(C_1)},\dots,\sqrt{D(C_c)})$ 与 $b=(1,\dots,1)$ 应用 Cauchy–Schwarz 不等式 $|\langle a,b\rangle|\le\|a\|\,\|b\|$：

$$
\sum_{j=1}^{c}\sqrt{D(C_j)}
=\langle a,b\rangle
\le\sqrt{\sum_{j=1}^{c}D(C_j)}\cdot\sqrt{\sum_{j=1}^{c}1}
=\sqrt{2m}\cdot\sqrt{c}
=\sqrt{2mc},
$$

其中最后一步代入了上面算出的 $\sum_j D(C_j)=2m$。每一步乘上最小值查找的成本记号即得结论。Q.E.D.

这个不等式说的是：固定槽位总量 $2m$ 时，各分量 $\sqrt{D(C_j)}$ 之和在分量**大小均匀**时达到最大，最大值是 $\sqrt{2mc}$。分量数 $c$ 越小，一轮越便宜——这为下面的轮次求和埋下伏笔。

### 2.4 轮次求和与总复杂度

由 Borůvka 的减半性质，第 $t$ 轮（$t=0,1,2,\dots$）开始时分量数满足

$$
c_t\le\frac{n}{2^t}.
$$

把单轮成本代入并求和：

$$
\sum_{t}O(\sqrt{2mc_t})
=\sum_{t=0}^{\lceil\log_2 n\rceil}O\!\left(\sqrt{\frac{2mn}{2^t}}\right)
=O\!\left(\sqrt{2mn}\sum_{t\ge0}2^{-t/2}\right).
$$

括号里的几何级数是收敛的，可以精确算出：公比 $r=2^{-1/2}<1$，故

$$
\sum_{t=0}^{\infty}2^{-t/2}=\frac{1}{1-2^{-1/2}}=\frac{\sqrt2}{\sqrt2-1}=\sqrt2\,(\sqrt2+1)=2+\sqrt2\approx3.414,
$$

其中第三个等号用了分母有理化 $\frac{1}{\sqrt2-1}=\frac{\sqrt2+1}{(\sqrt2-1)(\sqrt2+1)}=\sqrt2+1$。于是总成本为

$$
O\!\left((2+\sqrt2)\sqrt{2mn}\right)=O(\sqrt{mn}).
$$

值得停下来看看这个求和的结构：成本的几何衰减来自“每轮分量数减半”，而每轮的 $\sqrt{\cdot}$ 又来自量子搜索——两个平方根（Grover 的 $\sqrt{D}$ 与 Cauchy–Schwarz 的 $\sqrt{c}$）相乘，再对轮次求几何级数，最终得到 $\sqrt{nm}$。复杂度表达式中每个因子的来源至此全部落定：$n$ 来自初始分量数，$m$ 来自槽位总量 $2m$，整体的开方来自量子最小值查找。

Dürr–Heiligman–Høyer–Mhalla 同时给出了匹配的量子下界 $\Omega(\sqrt{nm})$（用 adversary 方法把 MST 归约到在 $\Theta(nm)$ 规模的搜索空间里找隐藏边）。因此在 array 模型下 MST 的查询复杂度是精确的 $\Theta(\sqrt{nm})$。代入两个极端情形验证自洽性：

- **稀疏图** $m=O(n)$：$\sqrt{nm}=\Theta(n)$，与连通性的复杂度同阶；
- **稠密图** $m=\Theta(n^2)$：$\sqrt{nm}=\Theta(n^{3/2})$，恰好回到邻接矩阵模型的复杂度——这是合理的，因为稠密图里两个模型能提供的每比特信息量趋于一致。

(connectivity-linear)=
## 3. 为什么无权连通性可以进一步降到 $\Theta(n)$

如果只需要**判定图是否连通**（并输出一棵生成森林作为证据），可以比 $\Theta(\sqrt{nm})$ 更省。直觉上有两个原因。

**第一，不必比较边权。** MST 必须在候选出边中找**最轻**的那条，这要求量子最小值查找；而连通性只需要**任意一条**出边——用普通的 Grover 搜索（在 $D(C)$ 个槽中找“邻居落在 $C$ 外”的槽）即可，无须维护阈值、无须重复搜索。更重要的是，Grover 搜索的成本可以与**命中数**挂钩：若分量 $C$ 有 $M_C\ge1$ 个槽指向外部，BBHT 搜索只需 $O(\sqrt{D(C)/M_C})$ 次查询——边界越大，找得越快。

**第二，失败本身就是信息。** 如果对分量 $C$ 的搜索失败了（在足够预算内没有找到任何出边），那就**证明**了 $C$ 是图的一个完整连通分量——这是一个永久性的结论，不需要复查。而在 MST 里，即使某一轮找不到更轻的边，下一轮仍要重新比较。

Dürr–Heiligman–Høyer–Mhalla 的 $\Theta(n)$ 算法把这两点组织成一个记账（amortization）论证。这里只讲思路，完整的常数与细节见原文：

1. 算法维护生成森林，对每个活跃分量在其邻接槽中 Grover 搜索一条出边，找到后立即合并；
2. **成功搜索的账记到新并入的顶点上**：搜索预算随分量规模指数翻倍（预算 $1,2,4,\dots$），因此同一个顶点所属的分量每扩大一倍才为它重新支付一次搜索成本，每个顶点在整个算法中至多被摊还 $O(\log n)$ 次，且单次摊还成本随边界规模而下降；
3. **失败的搜索只在预算翻倍到覆盖整个分量时才发生**，此时该分量已被证明是最终连通分量，成本一次性摊给它内部的顶点和槽位，永不再付。

综合起来，全部搜索成本被摊还到 $n$ 个顶点头上，总计 $O(n)$ 次查询。与之匹配的 $\Omega(n)$ 下界即使在稀疏图上也成立：例如区分“一个 $n$ 元环”与“两个不相交的环”，等价于在 $\Theta(n)$ 个槽中搜索被对手藏起来的那条差异边，量子搜索也需要 $\Omega(\sqrt{2n\cdot 1})=\Omega(n)$ 量级的查询（这是 Grover 下界的直接推论）。

值得指出的一点是：如果图是**稀疏**的（$m=O(n)$），其实不需要上述精巧记账——直接把第 2 节 Borůvka 框架里的“最小值查找”换成“任意出边搜索”，同样的 Cauchy–Schwarz 求和就给出 $O(\sqrt{mn})=O(n)$。记账论证真正的价值在**稠密**情形：当 $m=\Theta(n^2)$ 时，朴素求和只给 $O(n^{3/2})$，必须靠“成本随命中数 $M_C$ 下降 + 失败只发生一次 + 预算翻倍”这三件事才能把稠密图的连通性也压到 $\Theta(n)$。也就是说，稠密图的 $\Theta(n)$ 比稀疏图深刻得多，这也是邻接表模型相对邻接矩阵模型（连通性为 $\Theta(n^{3/2})$）拉开差距的地方。

有一个常见的误解必须澄清：$\Theta(n)$ **不表示可以列出全部 $m$ 条边**。算法只需要输出一棵生成树，即 $n-1$ 条边，所以 $\Theta(n)$ 与输出规模自洽；如果任务要求枚举全图（例如读入整个邻接表），那么光输出就有 $\Omega(m)$ 的规模，任何算法都不可能低于这个数。查询复杂度永远要和输出规模一起讨论。

## 4. 性质测试与精确判定的区别

(property-testing-promise)=
### 4.1 从精确判定到“远/近”二分法

先看重判定的难度。**精确的二分图判定**要求发现图中哪怕只藏着**一个**奇环：一条边、一个环的差别就翻转答案。用对手论证可以把这种脆弱性变成下界：取一张二分图 $G$，再构造只比 $G$ 多一条内部边（从而含奇环）的 $G'$；区分二者等价于在 $\Theta(dn)$ 个槽中定位那条被藏起来的边。这正是一个 $N=\Theta(n)$ 规模的无结构搜索，量子算法也要 $\Omega(\sqrt n)$；而一般位置上的精确判定（没有任何稀疏/有界度承诺）下界更高。总之，**精确判定只允许多项式级（开平方）的量子收益**，没有指数加速的空间。

**性质测试（property testing）** 换了一个承诺更弱、但在很多应用场景中同样有用的问题。在有界度模型（$d_v\le d=O(1)$，共 $dn$ 个槽）下，二分性 tester 只需以高概率（比如 $\ge2/3$）区分两种情形：

- 图是二分图（必须接受）；或
- 图是 **$\epsilon$-远**于二分图的（必须拒绝），即至少要修改 $\epsilon dn$ 个邻接槽才能把它变成二分图。

对既不满足前者也不满足后者的“中间”输入——差一点点就二分的图——tester 的回答不受任何约束。这个“承诺缺口”正是复杂度的救命稻草：$\epsilon$-远的图不是在某一处藏着一个小缺陷，而是**到处都有缺陷**——你必须删掉输入的常数比例才能修好它。直觉上，坏结构如此密集，以至于**局部的随机探查会以不可忽略的概率撞上它**。性质测试的全部艺术就在于把这个直觉变成统计上可检测的信号，而量子算法的任务则是把“收集统计信号”这一步加速。

(parity-collision-birthday)=
### 4.2 随机游走与奇偶碰撞

Goldreich–Ron 型经典 tester 的做法：从随机选取的起点发出许多条长度为 $L=\operatorname{poly}(1/\epsilon)$ 的随机游走。分析（其细节超出本课范围）表明：若图 $\epsilon$-远离二分图，则存在一个不可忽略比例的起点的邻域内，**同一个终点 $w$ 既可以由偶数长度的路径、也可以由奇数长度的路径从同一起点到达**。而在二分图中，路径的奇偶性由终点的所在侧唯一决定，这种“奇偶冲突”绝不发生。于是“找到一对奇偶性不同、终点相同的游走”就是远离二分性的统计证书。

后一句话值得证一下，它是整个 tester 的逻辑支点。

**引理（二分图的奇偶一致性）.** 设 $G$ 是二分图，$s$ 是任意顶点。则从 $s$ 到任一顶点 $w$ 的所有路径长度具有相同的奇偶性。

**证明.** 设 $G$ 的二分划为 $(A,B)$，不妨 $s\in A$。沿任何一条从 $s$ 出发的路径走，每跨一条边就换一次侧（二分图的边全部横跨 $A$、$B$）。因此走偶数步后必回到 $A$ 侧，走奇数步后必落在 $B$ 侧：终点所在侧由路径长度的奇偶性唯一决定。若存在从 $s$ 到 $w$ 的两条路径长度奇偶不同，则 $w$ 既要属于 $A$ 侧又要属于 $B$ 侧，矛盾。Q.E.D.

反过来说，**“同一起点、同一终点、奇偶不同”的一对路径蕴含着闭奇行走**（把两条路径首尾相接即得长度为奇数的闭行走，而闭奇行走必含奇环），即蕴含非二分性。所以奇偶碰撞对二分性是“永不误报、远则必现”的证书：二分图中它不存在（上面的引理），$\epsilon$-远的图中它大量存在（Goldreich–Ron 的分析）。

把每条随机游走由一个**种子（seed）** $s$ 完全确定（种子编码起点和每一步在邻居列表中的选择），定义映射

$$
F(s)=(\text{终点},\ \text{路径长度的奇偶}),
$$

则任务化为：**在种子空间中寻找一对碰撞**——$F(s_1)=F(s_2)$ 且两条游走的奇偶分量不同（可以把奇偶并入函数值，即标准的“找碰撞/元素互异”问题）。

### 4.3 生日界与 $n^{1/3}$ 的来源

先算经典需要多少样本。设我们采集 $K$ 个独立的游走种子，每个的终点近似均匀地落在 $n$ 个顶点之一（在“远离二分”的坏图中，碰撞概率只会更高，所以用均匀情形估算所需样本量是合理的）。$K$ 个样本两两**不发生**终点碰撞的概率为

$$
\prod_{j=0}^{K-1}\left(1-\frac{j}{n}\right)
\le\prod_{j=0}^{K-1}e^{-j/n}
=\exp\!\left(-\frac{1}{n}\sum_{j=0}^{K-1}j\right)
=\exp\!\left(-\frac{K(K-1)}{2n}\right),
$$

其中第一步用了标准不等式 $1-x\le e^{-x}$（对一切实数 $x$ 成立，可由 $e^{-x}$ 在 $0$ 处的切线性质看出）。要让碰撞以常数概率发生，需要指数部分为常数，即 $\frac{K^2}{2n}\sim\ln2$，解出

$$
K=\Theta(\sqrt n).
$$

这就是著名的**生日界**：经典 tester 必须生成约 $\sqrt n$ 条游走才能期望看到一次碰撞，经典复杂度因此被钉在 $\widetilde\Theta(\sqrt n)$ 量级（乘上游走长度 $\operatorname{poly}(1/\epsilon)$ 与若干对数因子）。

量子加速的扳机是**元素互异性**：在 $K$ 个元素（这里是 $K$ 个函数值 $F(s_1),\dots,F(s_K)$）中找一对相等者，量子查询复杂度是 $\Theta(K^{2/3})$——对比经典所需的 $\Theta(K)$ 与朴素 Grover 会猜到的 $\sqrt K$。把“查询一个函数值”实现为对 walk-seed oracle 的一次相干求值，并以去随机化的游走族保证 $F$ 可以由短种子确定性地算出（第 6 节详述），就可以把整个 tester 包进元素互异性算法：

$$
O(K^{2/3})\quad\text{次查询，取}\quad K=\Theta(\sqrt n)
\quad\Longrightarrow\quad O\!\left((n^{1/2})^{2/3}\right)=O(n^{1/3}).
$$

这就是 $n^{1/3}$ 这个指数的全部来源：**生日界贡献 $\sqrt n$ 个样本，元素互异性把样本数的查询代价压到 $2/3$ 次幂**，两个指数相乘：$\frac12\times\frac23=\frac13$。代价函数中省略的因子包括游走长度 $L=\operatorname{poly}(1/\epsilon)$、固定度界 $d$ 带来的常数，以及若干 polylog 因子——所以准确的说法是：固定 $d,\epsilon$ 时，查询复杂度为 $O(n^{1/3})$，省去 polylog 与精度因子。

(expansion-testing)=
## 5. 扩展性测试（expansion testing）

**扩展图（expander）** 是“任何小顶点集合都有大量边指出集合之外”的图；与之相对，差的图存在**瓶颈（bottleneck）**：一个不小的集合只有很少出边，随机游走一旦走进去就很难出来。扩展性测试要区分“图是足够好的扩展图”与“图离任何扩展图都很远”。

这个问题同样能被翻译成碰撞统计的语言，而且物理图像很清晰：

- **差扩展图**：瓶颈限制了游走的扩散，从同一个种子邻域出发的多条游走，其终点会**集中**在一个小区域里。若终点分布集中在大小为 $b$ 的集合上，则两个独立终点相撞的概率至少为 $\frac{1}{b}$（直接计算：$\sum_w p_w^2\ge\frac{1}{b}$，由 Cauchy–Schwarz 或均方-均值不等式，当 $p_w$ 支撑在 $b$ 个点上时 $\sum_w p_w^2\cdot b\ge(\sum_w p_w)^2=1$）。瓶颈越小，$b$ 越小，碰撞越频繁。
- **好扩展图**：随机游走混合（mixing）快，终点分布接近均匀，碰撞率约为 $\frac{1}{n}$——这是 $n$ 个顶点上能达到的最低碰撞率。

代入具体数字感受一下这个差距。取 $n=10^4$：若终点近均匀，一次独立采样的两条游走相撞的概率约为 $\frac1n=10^{-4}$；若瓶颈把终点分布压缩到 $b=100$ 个顶点的集合上，碰撞率至少为 $\frac1b=10^{-2}$，整整高出两个数量级。采集 $K$ 条游走产生 $\binom K2$ 对候选碰撞，$K=\Theta(\sqrt n)=100$ 条游走在坏图中期望看到 $\binom{100}{2}\times10^{-2}\approx50$ 次碰撞，在好图中只有 $\binom{100}{2}\times10^{-4}\approx0.5$ 次——统计上清晰可分。当然，真实算法的难点在于终点分布既不严格均匀也不严格集中，需要用 $\operatorname{poly}(1/\epsilon)$ 长度的游走把差距放大到可检测，这正是精度因子进入复杂度的地方。

因此“终点碰撞率显著高于 $\frac1n$”就是瓶颈的统计信号。量子算法沿用上一节的框架：把经典 random-walk collision statistic 的采样过程交给元素互异性子程序（配合量子计数估计碰撞率），得到同样的上界

$$
O(n^{1/3})
$$

次查询（固定 $d,\epsilon$ 与扩展参数，省略 polylog 与精度因子）。

两个保留条款必须说清楚：

1. **下界与指数空隙。** 该问题已知的量子下界是 $\Omega(n^{1/4})$。这排除了指数级加速（$n^{1/4}$ 仍是多项式量级），但在 $\frac14$ 与 $\frac13$ 两个指数之间留着一个未闭合的空隙——当前最好的算法与最好的下界并不匹配，这是公开问题。
2. **gap 承诺不可省略。** 性质测试的定义中必须固定允许的扩展缺口（expansion gap），即“好图”的扩展参数要比“坏图”显著大出一截。没有 gap 的**精确**谱扩展判定（例如“第二大特征值是否恰好不超过某个阈值”）是另一个完全不同的任务，不适用这里的 $n^{1/3}$ 界，也不能套用随机游走碰撞的论证——因为碰撞统计只能区分统计上可分辨的两个分布族，无法执行精确的谱计算。

(reversible-walk-implementation)=
## 6. 时间、空间与可逆随机游走

到目前为止我们讨论的都是**查询**复杂度。要把这些算法落到实处，还必须回答：每次“查询 $F(s)$”要花多少基本操作？需要多少量子内存？

**单次求值的成本。** 计算 $F(s)$ 需要相干地模拟一条长度为 $L$ 的随机游走。具体地说，工作寄存器保持“当前顶点 $v$、步数计数器、以及种子的当前段”；第 $\ell$ 步做三件事：

1. 从种子（或其伪随机展开）读出本步要选的邻居下标 $i_\ell\in\{1,\dots,d\}$；
2. 调用一次 $O_L$，把 $|v,i_\ell,0\rangle$ 映为 $|v,i_\ell,\operatorname{nbr}(v,i_\ell)\rangle$，再把新顶点交换进当前顶点寄存器；
3. 计数器加一，并把不再需要的旧信息用逆运算清除。

因此一次 $F$ 求值 = $L$ 次邻接表查询 + $O(L)$ 个基本门，结束时寄存器里只有 $(\text{终点},\text{奇偶})$ 与种子本身。代回元素互异性框架，总时间复杂度为 $\widetilde O(n^{1/3}\cdot L)$；固定性质参数（$d,\epsilon$ 与扩展 gap）后 $L=\operatorname{poly}(1/\epsilon)$ 是与 $n$ 无关的因子，时间尺度保持 $\widetilde O(n^{1/3})$。

**空间问题与可逆化。** 朴素的模拟会把整条路径存下来：$L$ 个顶点，每个 $\log n$ 比特，共 $O(L\log n)$ 的内存——而且中间结果还牵扯到**可逆性**：量子计算机上一切演化必须可逆，随机选择不能“丢弃”，必须要么保留、要么**可逆清除（uncompute）**。解决方案是把两件标准工具组合起来：

1. **去随机化游走族（derandomized walk family）**：不用真随机比特驱动游走，而是让整条游走成为短种子的确定性函数，同时保留所需的碰撞统计性质。这样“随机选择”不需要存储，需要时从种子**重新计算**即可；
2. **可逆迭代与嵌套数据结构**：每算完一步就把不再需要的中间顶点用逆运算擦除，使工作空间只随种子长度和当前状态增长。

Cade、Montanaro 与 Belovs（Zoo 编号 317）沿着这条路线给出了 cycle/bipartiteness 测试的时间空间高效实现：在固定性质参数下，空间可以压到 polylog 量级，同时保持 $\widetilde O(n^{1/3})$ 的时间尺度。这也是本课所有 $n^{1/3}$ 结果从“查询复杂度”升级为“可实际实现算法”的关键一步。

最后列出模型层面必须写进承诺（promise）的细节，否则上述界都可能失效：

- **邻接表顺序是任意的。** oracle 返回的“第 $i$ 个邻居”可以由对手任意排列，算法不得假定同一顶点的邻居已按编号排序，也不得利用列表顺序传递的信息；
- **多重边与自环。** 若输入允许重边或自环，槽位计数 $2m$、碰撞概率、距离定义都会相应变化，必须在输入承诺中明确；
- **无向对称槽。** 每条无向边在两个端点的列表中各出现一次，算法必须正确处理这种重复，且任何“修改槽位”的距离度量都要考虑两端的一致性约束。

## 7. 小例子

**例 1（路径图 $P_n$）.** 路径图有 $m=n-1$，它本身就是一棵树，所以 MST 就是它自身。代入公式：

$$
\sqrt{nm}=\sqrt{n(n-1)}=n\sqrt{1-\tfrac1n}
=n\left(1-\frac{1}{2n}+O\!\left(\tfrac{1}{n^2}\right)\right)
=n-\frac12+O\!\left(\tfrac1n\right)=\Theta(n),
$$

其中第三个等号用了 Taylor 展开 $\sqrt{1-x}=1-\frac{x}{2}+O(x^2)$（$x=\frac1n$）。即路径图上的 MST 查询复杂度是 $\Theta(n)$——与它作为稀疏图的身份相符。

**例 2（完全图 $K_n$）.** 完全图有 $m=\frac{n(n-1)}{2}=\Theta(n^2)$，于是

$$
\sqrt{nm}=\sqrt{n\cdot\frac{n(n-1)}{2}}=n\sqrt{\frac{n-1}{2}}\approx\frac{n^{3/2}}{\sqrt2}=\Theta(n^{3/2}),
$$

与邻接矩阵模型的 MST 复杂度一致。两个模型在稠密端汇合，在稀疏端分开，这正是公式 $\sqrt{nm}$ 的图像。

**例 3（Cauchy–Schwarz 单轮界的数值验证）.** 设某一轮有两个分量，$D(C_1)=12$、$D(C_2)=8$，则 $2m=\sum_jD(C_j)=20$，即 $m=10$，$c=2$。不等式左边为

$$
\sqrt{12}+\sqrt{8}=2\sqrt3+2\sqrt2\approx3.464+2.828=6.292,
$$

右边为

$$
\sqrt{2mc}=\sqrt{2\cdot10\cdot2}=\sqrt{40}\approx6.325.
$$

左边确实不超过右边，且两边相当接近——这个例子里两个分量的大小（$12$ 与 $8$）比较均匀，接近 Cauchy–Schwarz 取等条件（各分量相等时取等），所以界几乎是紧的。

**例 4（$n^{1/3}$ 的数值感受）.** 取 $n=10^6$。经典 tester 需要 $K\approx\sqrt n=10^3$ 条游走才能以常数概率撞见一次终点碰撞，每条游走要逐步采样，故经典查询量级为 $10^3$（乘以游走长度）。量子算法对这 $K=10^3$ 个种子做元素互异性，查询数为

$$
K^{2/3}=(10^3)^{2/3}=10^2=n^{1/3},
$$

即约一百次相干求值——每一“次”内部仍包含 $L$ 步邻接表查询，但样本收集本身获得了 $K^{1/3}$ 的加速。这个例子也说明了省略 polylog 因子的记法在实际规模上的含义：指数收益 $\frac12\to\frac13$ 是实打实的，但常数与 $L=\operatorname{poly}(1/\epsilon)$ 因子在小规模输入上可能盖过它。

**例 5（奇环与 $\epsilon$-远）.** 奇环 $C_{2r+1}$（$n=2r+1$ 个顶点）不是二分图，但只要删除**任意一条边**就变成一条路径，从而是二分图。在有界度模型中 $d=2$，总槽数 $dn=2n$；删除一条边相当于修改它的两个对称槽，即改动 $2$ 个槽。按定义，图是 $\epsilon$-远的当且仅当所需修改数 $\ge\epsilon dn$：

$$
2\ge\epsilon\cdot 2n\iff\epsilon\le\frac1n.
$$

也就是说，只有当我们把“远”的标准放宽到 $\epsilon\le\frac1n$ 时，长奇环才算“远离二分图”；对任何**常数** $\epsilon$（比如 $\epsilon=0.01$，只要 $n>100$），长奇环都不是 $\epsilon$-远的，性质 tester 对它**不作任何承诺**——接受或拒绝都算对。这不是算法的缺陷，而是 promise 的精确含义：单个、拉得很长的坏结构在统计上是不可检测的，tester 只保证抓住“遍布全图”的坏结构。

## 8. 小结

- 邻接表的总搜索空间是 $2m$ 个槽，而非 $n^2$ 个潜在边——稀疏图因此获得实质收益；
- Borůvka 框架下，分量槽数的平方根经 Cauchy–Schwarz 求和得单轮 $O(\sqrt{2mc})$，再对分量减半的几何级数求和得 MST 的 $\Theta(\sqrt{nm})$，且有匹配下界；
- 无权连通性只找**任意**出边，配合失败即证明、预算翻倍与摊还记账，可达 $\Theta(n)$；但这不包含输出全部 $m$ 条边；
- 有界度性质测试把“$\epsilon$-远”的承诺转成大量随机游走终点上的奇偶碰撞；生日界要求 $\Theta(\sqrt n)$ 个样本，元素互异性把样本查询压到 $2/3$ 次幂，合起来是 $O(n^{1/3})$；
- 扩展性测试复用同一碰撞框架，上界 $O(n^{1/3})$、下界 $\Omega(n^{1/4})$，且必须固定扩展 gap；
- 查询复杂度落地为算法需要去随机化游走族与可逆清除，空间可压到 polylog，时间保持 $\widetilde O(n^{1/3})$。

## 练习题

**练习 1【邻接表 oracle 与握手引理】**（→ [第 1 节](#array-oracle-model)）

1. 基础：设 $n=5$ 的图度序列为 $(4,3,2,2,1)$，用握手引理计算邻接表总槽位数与边数 $m$，并写出枚举顶点 2 的全部邻居所需的查询次数。
2. 进阶：分别比较“判定 $(u,v)$ 是否有边”与“求 $v$ 的第 $i$ 个邻居”这两个操作在邻接表模型与邻接矩阵模型下的量子查询成本，解释为什么说邻接表模型“让枚举邻居变便宜、却让确认非边失去直接入口”。

> 提示：前一个操作在邻接表下要在 $d_v$ 个槽中搜索 $u$，在邻接矩阵下只需一次查询；后一个操作正好相反。

**练习 2【量子最小值查找】**（→ [2.2 节](#quantum-minimum-finding)）

1. 基础：复述 Dürr–Høyer 算法的三步循环，指出每次 Grover 搜索的命中集合是什么，并写出在 $N$ 个元素中找最小者的期望查询复杂度。
2. 进阶：设某次搜索前当前阈值在全体元素中排第 $r$，写出该次搜索的期望成本；再解释“新阈值的期望排名约为 $r/2$”为何使各次搜索成本构成公比 $\sqrt2$ 的几何级数、并由末项 $O(\sqrt N)$ 主导。

> 提示：命中数为 $r$ 时 BBHT 成本为 $O(\sqrt{N/r})$，把各项 $O(\sqrt{N/r_k})$ 沿 $r_k\approx r_0/2^k$ 求和后比较首末两项。

**练习 3【Cauchy–Schwarz 单轮界与轮次求和】**（→ [2.3 节](#cauchy-schwarz-round-summation)）

1. 基础：分别计算 $m=n$、$m=n^{3/2}$、$m=n^2$ 时 MST 查询复杂度 $\sqrt{nm}$ 的指数，并验证 $m=n^2$ 时与邻接矩阵模型的 $\Theta(n^{3/2})$ 一致。
2. 进阶：从 $D(C)=\sum_{v\in C}d_v$ 与 $\sum_vd_v=2m$ 出发，完整写出一轮 Borůvka 成本 $\sum_{j=1}^c\sqrt{D(C_j)}\le\sqrt{2mc}$ 的推导，并指出等号成立的条件（分量满足什么关系时取等）。

> 提示：对向量 $(\sqrt{D(C_1)},\dots,\sqrt{D(C_c)})$ 与全 $1$ 向量应用 Cauchy–Schwarz，取等当且仅当二者成比例。

**练习 4【连通性的线性复杂度】**（→ [第 3 节](#connectivity-linear)）

1. 基础：列出连通性算法相对 MST 的两点节省（不必比较边权、失败即是信息），并写出分量 $C$ 有 $M_C$ 个指向外部的槽时 Grover 搜索一条出边的成本。
2. 进阶：解释区分“一个 $n$ 元环”与“两个不相交的环”为何需要 $\Omega(n)$ 次查询；再说明为什么 $\Theta(n)$ 的连通性算法不能用来在 $o(m)$ 次查询内枚举全部 $m$ 条边。

> 提示：前者等价于在 $\Theta(n)$ 个槽中找一条被对手藏起来的差异边；后者的输出规模本身是 $\Omega(m)$。

**练习 5【性质测试的远/近承诺】**（→ [4.1 节](#property-testing-promise)）

1. 基础：写出有界度模型与“$\epsilon$-远”的定义；设 $d=2$、$n=100$、$\epsilon=0.01$，计算一张图成为 $\epsilon$-远至少需要修改多少个邻接槽。
2. 进阶：设 $n$ 为奇数，计算环 $C_n$ 在有界度模型（$d=2$）下离二分性的距离（以槽数计），并求出使它成为 $\epsilon$-远的最大 $\epsilon$；由此解释为什么性质 tester 不保证以常数查询发现单个长奇环。

> 提示：删掉任意一条边就把奇环变成路径；一条边占据两个对称槽，与阈值 $\epsilon dn=2\epsilon n$ 比较。

**练习 6【奇偶碰撞证书与生日界】**（→ [4.2 节](#parity-collision-birthday)）

1. 基础：写出 $F(s)=(\text{终点},\ \text{路径长度的奇偶})$ 的定义，并解释“同一起点、同一终点、奇偶不同”的一对路径为何是二分性的否定证书（永不误报）。
2. 进阶：证明二分图的奇偶一致性引理：设 $G$ 是二分图、$s$ 是任意顶点，则从 $s$ 到任一顶点的所有路径长度具有相同的奇偶性。
3. 进阶：推导生日界：$K$ 个近似均匀的终点样本中无碰撞的概率至多为 $\exp(-\frac{K(K-1)}{2n})$，并由此说明经典 tester 为何需要 $K=\Theta(\sqrt n)$；再验证取 $K=\Theta(\sqrt n)$ 时元素互异性的查询数 $O(K^{2/3})=O(n^{1/3})$。

> 提示：对乘积 $\prod_{j=0}^{K-1}(1-\frac jn)$ 用不等式 $1-x\le e^{-x}$，令指数部分为常数解出 $K$。

**练习 7【扩展性测试】**（→ [第 5 节](#expansion-testing)）

1. 基础：设 $n=10^4$，分别计算终点近似均匀与被瓶颈压缩到 $b=100$ 个顶点时两条独立游走的碰撞概率；再计算 $K=100$ 条游走产生的候选碰撞对数，并估计两种情形下的期望碰撞次数。
2. 进阶：解释为什么扩展性测试必须固定扩展 gap：构造两个扩展参数仅相差 $o(1)$ 的图族，说明随机游走碰撞统计无法以常数样本区分它们，从而“无 gap 的精确谱扩展判定”不属于同一任务。

> 提示：碰撞统计只能区分统计上可分辨的终点分布族；谱参数连续变化时，混合后的终点分布几乎相同。

**练习 8【可逆随机游走实现】**（→ [第 6 节](#reversible-walk-implementation)）

1. 基础：把一次 $F(s)$ 求值分解为对 $O_L$ 的查询次数与基本门数（游走长度为 $L$），并说明元素互异性框架下总时间为何是 $\widetilde O(n^{1/3}\cdot L)$。
2. 进阶：设计从 walk seed 到 $(\text{终点},\text{奇偶})$ 的可逆 oracle：说明每个寄存器的内容、每一步如何用一次 $O_L$ 更新当前顶点，以及如何用逆运算清除中间顶点，使得空间为 $O(\log n)$ 加种子长度量级（允许使用去随机化游走族作为假设）。

> 提示：每步把新顶点交换进寄存器后，立即对旧顶点的计算过程执行逆运算（uncompute）。

## 参考文献

- Zoo 编号 34：Dürr、Heiligman、Høyer 与 Mhalla, [Quantum Query Complexity of Some Graph Problems](https://arxiv.org/abs/quant-ph/0401091).
- Zoo 编号 144：Ambainis、Childs 与 Liu, [Quantum Property Testing for Bounded-Degree Graphs](https://arxiv.org/abs/1012.3174).
- Zoo 编号 317：Cade、Montanaro 与 Belovs 关于 cycle/bipartiteness 的时间空间高效实现。