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

邻接矩阵把任意非边查询也计为一次；邻接表 oracle 则直接返回某顶点的第 $i$ 个邻居。对稀疏图，这会从根本上改变复杂度：MST 可达 $\Theta(\sqrt{nm})$，exact connectivity 可达 $\Theta(n)$；若只测试图是否远离二分图或扩展图，在有界度模型中量子查询甚至可降到 $O(n^{1/3})$。

## 1. Array / adjacency-list oracle

设图有 $n$ 顶点、$m$ 条无向边。Oracle 接收

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

返回第 $i$ 个邻居及可选边权：

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

数组总槽位 $\sum_vd_v=2m$。通常还给 degree oracle 或用特殊空标记补齐。相同边在两个端点列表出现，算法必须处理重复。

有界度模型进一步承诺 $d_v\le d=O(1)$，输入规模 $O(dn)$。性质测试中的“$\epsilon$-far”表示至少修改 $\epsilon dn$ 个邻接槽才能获得目标性质。

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

当前分量 $C$ 的邻接槽总数

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

在这些槽中用 quantum minimum finding 寻找最轻出边，成本

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

若一轮有 $c$ 个分量，Cauchy--Schwarz：

$$
\sum_C\sqrt{D(C)}
\le\sqrt{c\sum_CD(C)}
=\sqrt{2mc}.
$$

Borůvka 每轮让 $c$ 至少减半，从 $c=n$ 求和得到

$$
\sum_tO(\sqrt{mn/2^t})
=O(\sqrt{mn}).
$$

相应 lower bound 也为 $\Omega(\sqrt{nm})$，所以 array 模型下最优。稀疏 $m=O(n)$ 时变成 $\Theta(n)$；dense $m=\Theta(n^2)$ 时回到 $n^{3/2}$，与邻接矩阵一致。

## 3. 为什么无权 connectivity 可进一步精炼

若只需判断连通，不必比较边权。算法维护生成森林，对每个活跃分量在其邻接槽中 Grover 搜索一条出边；找到后合并。通过把成功搜索成本记到新加入的顶点/分量规模，并让失败搜索只在分量尺度翻倍时发生，可把重复扫描 amortize 到

$$
\Theta(n)
$$

查询，而不是机械套用所有加权 minimum。该界在 array 模型匹配 lower bound。

这不表示可以输出所有 $m$ 条边；算法只需 $n-1$ 条生成树边。若任务要求列出全图，输出规模仍为 $\Omega(m)$。

## 4. Property testing 与 exact decision 的区别

Exact bipartiteness 必须发现哪怕一个隐藏奇环；property tester 只承诺：

- 图是二分图；或
- 至少修改 $\epsilon dn$ 个槽才能变二分。

后者意味着坏结构在许多局部随机游走中留下统计信号。Goldreich--Ron 型 tester 从随机起点发出许多长度 $L=\operatorname{poly}(1/\epsilon)$ 的游走。若图远离二分，某些终点可由同一起点通过偶长和奇长路径同时到达。

把随机游走种子 $s$ 映到

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

寻找“终点相同、奇偶不同”的碰撞。经典要生成约 $\sqrt n$ 个样本才有生日碰撞；量子 element-distinctness/碰撞子程序对相干 walk-seed oracle 搜索，结合 derandomized walk family，将查询降到

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

（固定 $d,\epsilon$，省略 polylog/精度因子）。

## 5. Expansion testing

扩展性要求小集合有大量出边。差扩展图含 bottleneck，随机游走混合慢，多个种子更容易落到相同终点；好 expander 的终点近均匀，碰撞率较低。量子算法同样把经典 random-walk collision statistic 交给 element distinctness/量子计数，得到 $O(n^{1/3})$ 上界。

该问题还有 $\Omega(n^{1/4})$ 量子下界，排除了指数加速但留下 $1/4$ 与 $1/3$ 指数空隙。性质定义必须固定允许的 expansion gap；无 gap 的精确 spectral expansion 判定不是同一任务。

## 6. 时间、空间与可逆随机游走

查询一个随机游走终点需要相干执行 $L$ 次 neighbor oracle，并保留或可逆清除随机选择。若直接存所有路径会消耗 $O(L\log n)$ 空间；伪随机种子、可逆迭代和嵌套数据结构可把空间降到 polylog，同时保持

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

在固定性质参数下的时间尺度。

邻接表顺序可能由 oracle 任意排列；算法不能假定同一顶点邻居已排序。多重边、自环与无向对称槽也应在输入承诺中明确。

## 7. 小例子

路径图 $P_n$ 有 $m=n-1$，MST 就是自身，$\sqrt{nm}=\Theta(n)$。完全图有 $m=\Theta(n^2)$，array 与 matrix 模型 MST 都为 $\Theta(n^{3/2})$ 查询。

奇环 $C_{2r+1}$ 不是二分图，但只删除一条边即可变二分；当 $r$ 随 $n$ 大时，它未必是常数 $\epsilon$-far。因此 property tester 不保证以常数查询发现单个长奇环，这正体现 promise 的作用。

## 8. 小结与习题

- 邻接表总搜索空间是 $2m$ 个槽，适合稀疏图。
- Borůvka 分量槽数的平方根求和给出 $\Theta(\sqrt{nm})$ MST。
- Exact connectivity 可通过只找任意出边和 amortization 达到 $\Theta(n)$。
- 有界度性质测试把远离承诺转成大量随机游走碰撞，量子复杂度 $O(n^{1/3})$。

1. 推导一轮 Borůvka 的 $\sqrt{2mc}$ 上界。
2. 比较 $m=n,n^{3/2},n^2$ 时 MST 查询指数。
3. 解释单个长奇环为何不一定满足常数 far promise。
4. 设计从 walk seed 到 endpoint/parity 的可逆 oracle。

## 参考文献

- 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 的时间空间高效实现。