邻接矩阵模型图算法：连通性、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 关于 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 与稀疏图算法。