# 邻接矩阵模型图算法：连通性、MST、Minor 与三角形

给定 $n$ 顶点图，邻接矩阵 oracle 一次回答某对顶点是否有边；完整输入含 $\Theta(n^2)$ 个潜在边。量子算法常把“找一条满足条件的边”从线性扫描降为平方根搜索，使连通性与最小生成树达到 $\Theta(n^{3/2})$ 查询。本课再说明 span program、quantum walk 和 learning graph 如何处理 minor 与固定子图。

## 1. Oracle 与复杂度尺度

无权图 oracle 为

$$
O_G|u,v,z\rangle
=|u,v,z\oplus A_{uv}\rangle,
$$

其中 $A$ 是 $n\times n$ 邻接矩阵。加权图返回 $w(u,v)$ 或“无边”。查询任意 $(u,v)$ 成本相同，不论真实图是否稀疏；因此“图只有 $m$ 条边”不会自动让 entry-query 更便宜。

经典最坏情况下常需查看 $\Theta(n^2)$ 个 entry。量子下界通常通过把未查询边位置编码成无结构搜索，得到 $\Omega(n^{3/2})$ 或其他多项式尺度。

## 2. Borůvka + 量子最小值求 MST

Borůvka 算法维护当前连通分量。每轮为每个分量 $C$ 找一条最轻出边，并把这些边加入森林；分量数至少减半。

分量 $C$ 的候选边数至多

$$
|C|(n-|C|)\le n|C|.
$$

Dürr--Høyer minimum finding 用

$$
O(\sqrt{n|C|})
$$

查询找到最轻出边。若当前有 $c$ 个分量 $C_1,\ldots,C_c$，Cauchy--Schwarz 给出一轮成本

$$
\sum_{j=1}^cO(\sqrt{n|C_j|})
\le O\!\left(
\sqrt{c\,n\sum_j|C_j|}
\right)
=O(n\sqrt c).
$$

分量数序列 $n,n/2,n/4,\ldots$，故

$$
\sum_t n\sqrt{n/2^t}
=O(n^{3/2}).
$$

同样框架若只需连通性，可为每个分量找任意出边，仍为 $O(n^{3/2})$。相应 adversary/search 归约给 matching $\Omega(n^{3/2})$，所以两者查询最优。

## 3. 最短路与可达性

量子化 Dijkstra/Prim 的核心是从尚未确定的顶点或边中做 minimum finding，并用 Grover 搜索更新候选。单源最短路在该模型可达约

$$
O(n^{3/2}\operatorname{polylog}n)
$$

查询，但权值比较、优先结构和负权边承诺必须明确。

$s$--$t$ connectivity 有另一种 span-program 解释。把每条可能边对应输入向量；若 $s,t$ 连通，路径流是正 witness；若不连通，割势函数是负 witness。Witness size 与路径长度/有效电阻及 cut 参数相关，通用最坏仍约 $n^{3/2}$，但特定图承诺下可更细。双反射相位检测还能把空间压到 polylog qubits 并实现近似同阶门时间。

## 4. Sparse 与 minor-closed properties

图性质若所有 yes 图都只有 $O(n)$ 条边，称 sparse。许多 minor-closed 性质属于此类：平面性、森林、排除固定路径等。量子算法组合：

1. Grover 检查输入是否过于稠密；
2. 若保持稀疏，利用有限 forbidden subgraph 列表或 quantum walk 搜索局部证书；
3. 对无法由有限 forbidden subgraphs 描述的性质，用 adversary 构造证明 $\Theta(n^{3/2})$。

这里应纠正 Quantum Algorithm Zoo 当前文字中的指数笔误：Childs--Kothari 原论文在**邻接矩阵、$n$ 顶点**口径下给出多数 minor-closed properties 的

$$
\Theta(n^{3/2}),
$$

不是 $\Theta(n^{2/3})$。后者甚至小于读取一个顶点邻接行的自然尺度，且与原论文摘要不符。可由有限 forbidden subgraphs 描述的性质则是 $o(n^{3/2})$，具体指数依 forbidden graph 结构而定。

## 5. Triangle finding 的嵌套搜索

三角形是 $(u,v,w)$ 三条边均存在。最简单方法 Grover 搜索 $\binom n3$ 个三元组，成本 $O(n^{3/2})$。更好的 learning graph/quantum walk 共享已查询边：

1. 选择 $r$ 个顶点并查询其诱导子图，setup $O(r^2)$；
2. 行走替换少量顶点，只更新 $O(r)$ 条边；
3. 若缓存中有三角形直接接受；否则对外部第三顶点做 nested Grover/graph collision；
4. 按三角形顶点落入缓存的概率平衡 $r$ 与内外搜索。

经过扩展 learning graph 的非均匀流优化，Zoo 快照记录的查询上界为

$$
O(n^{5/4}).
$$

这不是把三个 edge queries 视为常数后直接 Grover 得到的；改进来自大量候选三角形共享边查询。稀疏图、固定更大子图和 3-uniform hypergraph 需要不同参数平衡。

## 6. 固定子图与 1-certificate

“包含固定 $H$”的 yes certificate 是 $H$ 的常数条边。Span program 与 learning graph 可按 $H$ 的 vertex cover、度数和边数设计流：先加载高复用顶点，再加载证书边。查询指数常写成这些图参数的函数，而非只有 $|V(H)|$。

若输入图承诺稀疏，找到 $H$ 的复杂度可能由

$$
\widetilde O\!\left(
n^{3/2-1/(\operatorname{vc}(H)+1)}
\right)
$$

型界控制；没有稀疏承诺时不能使用同一公式。Tree-minor detection 的 span program 则利用路径/流 witness，和枚举所有映射完全不同。

## 7. 查询、门与输出

邻接矩阵 oracle 可在叠加中访问任意边是强假设。若图实际以压缩 edge list 存储，模拟一次 $A_{uv}$ 可能需要字典查询。反过来，邻接表 oracle 能直接列邻居，却不擅长回答任意非边；下一课会看到复杂度随模型改变。

MST 输出 $n-1$ 条边，因此至少有 $\Omega(n)$ 输出时间；三角形判定只输出一比特。查询上界不能忽略可逆并查集、缓存边和 learning-graph reflection 的门成本。

## 8. 小结与习题

- 邻接矩阵含 $n^2$ 潜在边，量子搜索把许多图问题降到 $n^{3/2}$。
- Borůvka 每轮量子找各分量最轻出边，分量减半求和得到 $O(n^{3/2})$。
- Span program 用路径流与割 witness 表示 connectivity/minor。
- Triangle learning graph 通过共享边查询改进三元组 Grover。

1. 完整推导 Borůvka 各轮成本和几何级数。
2. 为 $s$--$t$ connectivity 写出一条路径流 witness 和一个割 witness。
3. 解释为什么 Zoo 中 $n^{2/3}$ 的 minor 指数与原论文 $n^{3/2}$ 冲突。
4. 比较三元组 Grover 与缓存 $r$ 点诱导子图的 setup/update。

## 参考文献与 Zoo 覆盖

- Zoo 34--36、52：[Dürr--Heiligman--Høyer--Mhalla](https://arxiv.org/abs/quant-ph/0401091) 关于 connectivity、MST 与 shortest paths。
- Zoo 140--141、152、240、272、317--318：minor-closed、quantum walk、span program、cycle/bipartite/st-connectivity。
- Zoo 21、70、153、171、175、241、276、319--320：triangle、固定子图、nested/extended learning graph 与稀疏图算法。