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

图论是量子查询算法最成功的应用领域之一。本课研究的是这样一个问题：给定一个只能用"问一条边是否存在"来访问的未知图，判定它的连通性、求最小生成树、检测子图，各需要问多少次？

这个问题之所以值得认真对待，有三个原因。第一，它是"量子平方加速"最干净的样板：许多图性质的经典查询复杂度是 $\Theta(n^2)$ 量级——本质上要把整张表读完——而量子算法普遍把它压到 $\Theta(n^{3/2})$，正好是 Grover 加速在结构化输入上的体现。第二，图查询模型提供了检验各种量子算法框架（Grover 搜索、量子行走、span program、learning graph）的统一试验场：同一个"找三角形"问题，用四种工具会得到四个不同的复杂度，比较它们本身就是理解这些工具的最好方式。第三，这里的结论几乎都是紧的：上界与下界在同一个多项式尺度上闭合，这在本教程前面的章节中并不多见。

本课的组织如下：第 1 节严格定义邻接矩阵 oracle 并建立复杂度尺度；第 2 节回顾所需的搜索工具；第 3 节完整推导连通性与最小生成树的 $\Theta(n^{3/2})$ 算法（这是本课的推导主线）；第 4 节讲匹配的下界；第 5 节讨论最短路与 span program 对可达性的解释；第 6 节处理稀疏与 minor-closed 图性质；第 7、8 节分析三角形与固定子图检测，这里 learning graph 会给出超过朴素 Grover 的加速；第 9 节讨论查询复杂度之外的实际问题。

历史背景（与文末参考文献对应）：经典侧的核心算法是 Borůvka 1926 年的最小生成树算法——它是历史上最早的 MST 算法，也是本课量子算法的外壳。量子侧的主线是 Dürr、Heiligman、Høyer、Mhalla 在 2004 年的工作（quant-ph/0401091，Zoo 34--36、52），他们系统给出了邻接矩阵模型下连通性、MST、最短路的量子算法与下界；其中用到的最小值查找子程序来自 Dürr--Høyer 1996。其后，量子行走框架（Ambainis、Szegedy、Magniez--Santha--Szegedy 等）与 span program 框架（Reichardt--Špalek 等）重新组织了这些结果并推向子图检测；Childs--Kothari 系统刻画了 minor-closed 图性质的量子查询复杂度；三角形检测的当前记录则由 learning graph 方法（Belovs 及其后的扩展）取得。这些归属的细节见各节与文末的 Zoo 条目。

前置知识：本课默认读者已掌握 Grover 搜索与振幅放大（第 3 章）、相位估计，以及"量子行走 = 两个反射的复合"这一基本图像（第 6 章）。我们会用到它们，但不重新推导。

本课知识点

邻接矩阵 oracle 与查询模型——写出无权与加权邻接矩阵 oracle 的作用方式，并解释为什么图稀疏不会自动降低 entry-query 模型的查询成本。
经典基准与对抗者下界——复述两半划分的对抗者策略，证明连通性判定的经典查询复杂度为 $\Theta(n^2)$，并说明量子下界为何需要更精细的构造。
单轮量子成本与几何级数——推导单分量成本 $O(\sqrt{n|C_j|})$，用 Cauchy--Schwarz 证明单轮总成本 $O(n\sqrt c)$，再对分量数减半的几何级数求和得到 $O(n^{3/2})$。
匹配下界与查询最优性——解释朴素搜索归约只给出 $\Omega(n)$ 的原因与"批量复用"机制，并说明精细 adversary 归约如何复现同一几何级数闭合为 $\Theta(n^{3/2})$。
Span program 见证结构——写出 $s$--$t$ 连通性的正 witness（路径流）与负 witness（割势）构造，并解释查询复杂度为何由两种 witness size 的几何平均决定。
稀疏与 minor-closed 性质——解释稀疏性与 minor-closed 性质的定义和三步算法策略，并辨析 Zoo 条目 $n^{2/3}$ 与原论文 $n^{3/2}$ 的指数冲突。
三角形与固定子图检测——计算三重 Grover 基线 $O(n^{3/2})$，推导缓存式量子行走的参数平衡 $r=n^{2/3}$ 得到 $O(n^{4/3})$，并说明向 $O(n^{5/4})$ 的改进为何来自共享边查询的复用。
查询复杂度之外——解释查询复杂度与时间、空间复杂度的区别，并论证 MST 的输出规模为何迫使任何算法的时间下界为 $\Omega(n)$。

1. 邻接矩阵 oracle 与复杂度尺度¶

1.1 问题与 oracle 的严格定义¶

设 $G=(V,E)$ 是一个 $n$ 顶点的简单无向图，$A$ 是它的 $n\times n$ 邻接矩阵 (adjacency matrix)：

\[\begin{split} A_{uv}= \begin{cases} 1, & \{u,v\}\in E,\\ 0, & \text{否则}. \end{cases} \end{split}\]

因为图是无向的，$A$ 对称且对角线为 $0$，所以独立的信息位只有上三角的 $\binom{n}{2}=\frac{n(n-1)}{2}$ 个。我们称每个位置 $(u,v)$ 为一个 entry。

邻接矩阵 oracle（无权情形） 是如下西算子：

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

其中 $u,v\in\{1,\ldots,n\}$ 是顶点索引，$z\in\{0,1\}$ 是答案比特，$\oplus$ 是模 2 加。这是标准的"XOR 型" oracle：输入一对顶点，它把"是否有边"异或到答案比特上。取 $|z\rangle=|-\rangle$ 就得到相位 oracle（第 3 章的标准转换），因此 Grover 类算法可以直接调用它。一次调用 $O_G$ 记为一次查询 (one query)；本课的复杂度默认指查询复杂度，即调用 $O_G$ 的次数。

对加权图，oracle 返回边权 $w(u,v)$（或一个特殊的"无边"标记）：

\[ O_G|u,v,z\rangle=|u,v,z\oplus w(u,v)\rangle, \]

其中 $z$ 寄存器要足够宽以容纳权值。除非特别说明，加权情形的查询成本与无权情形同阶。

1.2 这个模型的一个关键特征¶

请注意 oracle 的语义：查询任意一对 $(u,v)$ 的成本完全相同，不论真实图是稀疏还是稠密。 这一点初看显然，实际上决定了整课的难度结构。想象图只有 $m\ll n^2$ 条边——经典算法如果用邻接表存储，只需要扫过 $2m$ 个条目；但在邻接矩阵 oracle 下，"稀疏"这个事实本身也要靠查询去发现：你不知道哪些位置是 1，就仍然要面对全部 $\binom{n}{2}$ 个潜在 entry。换言之，"图只有 $m$ 条边"不会自动让 entry-query 模型更便宜；除非问题本身承诺了稀疏性（见第 6 节），复杂度分析都必须按最坏情况 $m=\Theta(n^2)$ 进行。

1.3 经典基准：为什么最坏情况要读完整张表¶

在比较量子算法之前，先确立经典基准。以连通性为例，我们论证任何确定性经典算法最坏情况下必须查询 $\Theta(n^2)$ 个 entry。

论证用对抗者（adversary）方法。把顶点集固定划分成两半 $V_1,V_2$，各 $n/2$ 个顶点。对抗者按如下策略回答查询：

若查询的 $(u,v)$ 落在同一半内部，回答"有边"；
若 $(u,v)$ 横跨两半，回答"无边"——除非这已经是最后一对尚未查询的跨半点对，此时才诚实回答。

在算法查询完最后一对跨半点对之前，它看到的回答与两种图都相容：一种是"两半各自成团、跨半只有这一条被查询的边"（连通），另一种是"两半各自成团、跨半没有任何边"（不连通）。因此算法无法提前停机，必须查询全部 $\frac{n}{2}\cdot\frac{n}{2}=\frac{n^2}{4}=\Theta(n^2)$ 个跨半 entry。这个论证可以严格化并推广到随机算法（Yao 原理），结论是：经典查询复杂度为 $\Theta(n^2)$。最小生成树、子图检测等问题的经典最坏情形同样是 $\Theta(n^2)$ 量级——本质上，"读完整张邻接矩阵"是不可避免的。

这就是量子算法的起点：经典侧必须线性扫描 $\Theta(n^2)$ 个位置，而 Grover 告诉我们"在 $N$ 个位置中找一个满足条件的位置"可以平方加速到 $O(\sqrt N)$。把 $N=\Theta(n^2)$ 代入，自然的目标就是 $O(n)$ 到 $O(n^{3/2})$ 之间的尺度；第 3 节会看到，对连通性与 MST，正确的答案是 $\Theta(n^{3/2})$。

1.4 量子下界的来源¶

量子侧为什么不能更快？通用的下界技术是把图问题归约到无结构搜索或其变体：构造一族图，使得某个未知边的位置编码了一个搜索实例的解，于是"判定图性质"蕴含"解决大小为 $N$ 的搜索"，从而继承搜索的 $\Omega(\sqrt N)$ 下界。对 $N=\Theta(n^2)$ 个 entry，这条路线直接给出 $\Omega(n)$；要得到更强的 $\Omega(n^{3/2})$（与第 3 节上界匹配），需要更精细的 adversary 构造，利用"图结构允许许多 entry 被批量复用"这一特点——这正是第 4 节的内容。此处只需记住尺度：量子下界通常通过把未查询边位置编码成无结构搜索得到，阶为 $\Omega(n^{3/2})$ 或其他多项式尺度，而不是 $\Omega(n^2)$ 或 $\Omega(\log n)$。

2. 预备：Grover 搜索与最小值查找¶

本课反复使用两个已知的量子子程序，这里只陈述接口与成本，推导见第 3 章。

Grover 搜索：设有一个相位 oracle 标记了 $M$ 个候选位置中的若干个（至少一个），则 $O(\sqrt M)$ 次查询能以高概率找到一个标记位置。若事先不知道标记个数，用指数增长的迭代次数猜测（"exponential search"），期望成本仍为 $O(\sqrt{M/t})$，其中 $t$ 是实际标记数。

Dürr--Høyer 最小值查找 (minimum finding)：设有 $M$ 个候选，每个候选 $(i,x_i)$ 可通过一次查询获得其键值 $x_i$。则存在量子算法用 $O(\sqrt M)$ 次查询、以高概率找到 $\arg\min_i x_i$。算法思想是 Grover 搜索的"自适应阈值"版本：维护当前最优候选 $j$，反复用 Grover 搜索"键值比 $x_j$ 更小"的位置（由指数搜索保证每次期望 $O(\sqrt{M/r})$ 次查询，$r$ 为更优候选数），找到就更新 $j$；对随机顺序的候选，期望更新次数为 $O(\log M)$，总成本 $O(\sqrt M)$。

一个技术性注记：这些子程序都有小的失败概率。本课的算法会把它们调用 $O(n)$ 或 $O(\log n)$ 次，通过每次分配 $O(\log n)$ 倍的重复把单次失败率压到 $1/\operatorname{poly}(n)$，再由 union bound 保证整体正确性。这只贡献对数因子，下面一律省略，并把子程序当作精确的来分析。

3. Borůvka + 量子最小值查找：MST 与连通性的 $\Theta(n^{3/2})$¶

本节是本课的推导主线。我们证明：

定理（Dürr--Heiligman--Høyer--Mhalla）：在邻接矩阵模型下，最小生成树与连通性判定的量子查询复杂度都是 $\Theta(n^{3/2})$。

上界 = 经典 Borůvka 算法的外壳 + 每轮内部的量子最小值查找；下界见第 4 节。

3.1 Borůvka 算法回顾¶

Borůvka 算法（1926）维护一个生成森林：初始时每个顶点自成一个连通分量，算法分轮进行，每一轮做两件事：

对当前每个连通分量 $C$，找一条离开 $C$ 的最轻的边（即一个端点在 $C$ 内、另一个端点在 $C$ 外的权值最小边）；
把所有这些边加入森林，合并相应的分量。

当只剩一个分量时，森林就是一棵最小生成树。

为什么这是对的（割性质）：对任意顶点集 $C$，离开 $C$ 的最轻边 $e$ 必属于某棵 MST。证明用交换论证：任取一棵 MST $T$，若 $e\notin T$，把 $e$ 加入 $T$ 会产生唯一一个环，这个环必然还有另一条边 $e'$ 离开 $C$（从 $C$ 出发的环必须回到 $C$）；由 $e$ 的最轻性 $w(e)\le w(e')$，于是 $T-e'+e$ 仍是生成树且权值不增。把这条性质应用到每个分量，就得到 Borůvka 每轮加入的边全部安全。

为什么轮数只有 $O(\log n)$：每条被加入的边至少合并两个分量，所以每轮之后分量数至少减半。严格地说，若当前有 $c$ 个分量，第 $t$ 轮后分量数 $c'$ 满足 $c'\le c/2$，故从 $c_0=n$ 出发，至多 $\lceil\log_2 n\rceil$ 轮结束。

3.2 单轮的量子成本¶

进入量子部分。设当前某一轮的分量为 $C_1,\ldots,C_c$，我们要为每个 $C_j$ 找最轻出边。

候选边数的估计。分量 $C_j$ 的出边形如 $(u,v)$，$u\in C_j$、$v\notin C_j$，故候选数至多为

\[ |C_j|\,(n-|C_j|)\le n\,|C_j|. \]

不等式就是 $n-|C_j|\le n$。注意我们用了 entry-query 模型的特点：这 $n|C_j|$ 个候选位置是已知的（由顶点对索引），未知的只是权值，因此"找最小键值的位置"正是 Dürr--Høyer 最小值查找的标准输入。

单分量成本。对分量 $C_j$ 应用最小值查找，查询数为

\[ O\!\left(\sqrt{n\,|C_j|}\right). \]

整轮成本：Cauchy--Schwarz 一步。对所有分量求和：

\[ \sum_{j=1}^{c}O\!\left(\sqrt{n\,|C_j|}\right) =O(\sqrt n)\cdot\sum_{j=1}^c\sqrt{|C_j|}. \]

对求和项用 Cauchy--Schwarz 不等式 $\big(\sum_j 1\cdot\sqrt{|C_j|}\big)^2\le\big(\sum_j 1^2\big)\big(\sum_j |C_j|\big)$，即

\[ \left(\sum_{j=1}^c\sqrt{|C_j|}\right)^2 \le c\cdot\sum_{j=1}^c|C_j| =c\,n, \]

其中第二个等号是因为各分量互不相交且覆盖全部 $n$ 个顶点。两边开方得 $\sum_j\sqrt{|C_j|}\le\sqrt{cn}$，代回：

\[ O(\sqrt n)\cdot\sqrt{cn}=O(n\sqrt c). \]

直观解读：一轮的成本不是 $c$ 个独立搜索成本的简单相加 $\sum_j\sqrt{n|C_j|}$（当分量大小悬殊时这个和可以很大），而是被"分量总顶点数只有 $n$"这一全局约束压着。最坏情形是所有分量等大（Cauchy--Schwarz 取等号的情形）：$c$ 个分量各含 $n/c$ 个顶点，每个搜索成本 $\sqrt{n\cdot n/c}=n/\sqrt c$，总成本 $c\cdot n/\sqrt c=n\sqrt c$，恰与上界一致。分量大小越悬殊，实际成本越小——这也是下界构造必须让分量均匀的原因。

3.3 轮间求和：几何级数¶

由 3.1 节，第 $t$ 轮开始时分量数 $c_t\le n/2^t$（$t=0,1,2,\ldots$）。把单轮成本代入并求和：

\[ \sum_{t\ge 0}O(n\sqrt{c_t}) \le O(n)\sum_{t\ge 0}\sqrt{\frac{n}{2^t}} =O(n^{3/2})\sum_{t\ge 0}2^{-t/2}. \]

几何级数收敛，比值 $2^{-1/2}$：

\[ \sum_{t\ge 0}2^{-t/2}=\frac{1}{1-2^{-1/2}}=\frac{1}{1-\frac{1}{\sqrt2}}\approx 3.414. \]

因此总查询数为

\[ O\!\left(\frac{n^{3/2}}{1-2^{-1/2}}\right)=O(n^{3/2}). \]

这一步值得停下来看一眼：成本的贡献随轮次几何衰减，第一轮（$c=n$，全是单点）独占约 $\frac{1}{3.414}\approx 29\%$ 之外的最大份额 $n\sqrt n=n^{3/2}$，后面所有轮次加起来只是同一量级。也就是说，"把 $n$ 个单点各自向外连一条边"这一件事本身就值 $n^{3/2}$ 次查询——这与第 4 节的下界图景完全吻合。

连通性判定是同一框架的退化情形：不需要比较权值，只需为每个分量找任意一条出边（Grover 搜索而非最小值查找），成本表达式逐项相同，仍为 $O(n^{3/2})$；若某轮某个分量找不到出边，图不连通。

3.4 一个可手算的小例子¶

取 $n=4$ 的加权图，顶点 $\{1,2,3,4\}$，权值

\[ w_{12}=1,\quad w_{34}=1,\quad w_{13}=5,\quad w_{14}=6,\quad w_{23}=7,\quad w_{24}=8. \]

第 1 轮：四个单点分量。各分量最轻出边：$1\to 2$（权 1），$2\to 1$（权 1），$3\to 4$（权 1），$4\to 3$（权 1）。加入边 $\{1,2\}$ 与 $\{3,4\}$（每条无向边只加一次），分量数从 4 减到 2：$\{1,2\}$ 与 $\{3,4\}$。

第 1 轮查询成本估计：每个分量 $C_j$ 满足 $|C_j|=1$，成本 $\sqrt{n|C_j|}=\sqrt 4=2$，四个分量共 $4\times 2=8$；上界公式给出 $n\sqrt c=4\sqrt 4=8$。两者相等——因为各分量等大，Cauchy--Schwarz 取等号。

第 2 轮：分量 $\{1,2\}$ 的出边候选为 $(1,3),(1,4),(2,3),(2,4)$，最轻的是 $w_{13}=5$；分量 $\{3,4\}$ 同理得 $5$。加入边 $\{1,3\}$，图连通，算法结束。MST 为 $\{1,2\},\{3,4\},\{1,3\}$，总权值 $1+1+5=7$。

第 2 轮成本估计：每个分量 $|C_j|=2$，候选边数 $\le n|C_j|=8$，成本 $\sqrt 8=2\sqrt2\approx 2.83$，两个分量共 $4\sqrt2\approx 5.66$；上界 $n\sqrt c=4\sqrt2\approx 5.66$，再次取等。

两轮合计 $\approx 13.7$，而总上界公式 $\frac{n^{3/2}}{1-2^{-1/2}}\approx 8\times 3.414\approx 27.3$。小例子确认了代数：当分量始终等大时，每轮都顶着上界走，几何衰减来自分量数的减半。

4. 下界：为什么 $n^{3/2}$ 是最优的¶

第 1.4 节说过，把单个未知边编码成搜索实例只给出 $\Omega(n)$。要匹配上界，需要更精细的 adversary/search 归约，这里给出核心图景而不展开全部技术细节。

为什么朴素的归约不够。如果把"两个各含 $n/2$ 顶点的团之间是否存在跨团边"编码成对 $\frac{n^2}{4}$ 个位置的 OR，连通性判定确实蕴含解这个 OR，量子下界为 $\Omega(\sqrt{n^2})=\Omega(n)$。但上界是 $O(n^{3/2})$，中间差了一个 $\sqrt n$。差额的来源是：上述实例中算法可以批量复用查询——Borůvka 第一轮用 $n$ 次 Grover 并行地在 $n$ 个单点中各自搜索，每个搜索只花 $\sqrt n$ 而不是 $n$，对抗者必须让"每个分量各自的搜索"都足够难，才能阻止这种复用。

精细归约的直觉。把顶点分成 $n$ 个"单点分量"阶段：隐藏一个由搜索实例控制的稀疏结构（例如一个未知的完美匹配或随机图的有无），使得算法在每一轮面对 $c$ 个分量时，每个分量都对应一个大小 $\Theta(n|C_j|)$ 的独立搜索问题。对每个分量单独套用搜索下界 $\Omega(\sqrt{n|C_j|})$，再对分量求和、对轮次求和，复现 3.2--3.3 节的同一个几何级数，得到 $\Omega(n^{3/2})$。Dürr--Heiligman--Høyer--Mhalla 的论文把这一图景严格化（对连通性与 MST 分别构造），结论是：

\[ \text{连通性与 MST 的量子查询复杂度都是 }\Theta(n^{3/2}), \]

即第 3 节的算法查询最优。这个"上界与下界在同一个几何级数上闭合"的现象值得记住：它说明 Borůvka + Grover 的结构不是巧合，而是问题本身的查询难度。

5. 最短路与 $s$--$t$ 可达性¶

5.1 量子化 Dijkstra 与 Prim¶

Dijkstra 单源最短路算法与 Prim 算法的经典结构是：维护一个"已确定"顶点集 $S$，每步从边界候选中取出键值最小者加入 $S$，并松弛相关边。量子化的思路与第 3 节一致：把每一步的"取最小"换成 Dürr--Høyer 最小值查找，把"找需要松弛的边"换成 Grover 搜索。候选结构比 Borůvka 复杂（键值会动态变化，需要小心处理优先队列的可逆实现），但查询尺度的来源相同：$n$ 轮、每轮在至多 $O(n)$ 量级的候选中做 $\sqrt{\cdot}$ 的搜索。综合结果：

\[ O\!\left(n^{3/2}\operatorname{polylog}n\right) \]

次查询可在邻接矩阵模型下求解单源最短路。引用这个结果时必须明确三个保留条款（原文已标注，此处解释）：

权值比较：键值是实数/整数权值，比较与加法必须精确到足够位宽，这贡献对数因子；
优先结构：动态键值需要可逆的数据结构支持，查询复杂度不变，但门复杂度会多出 $\operatorname{polylog}$ 因子；
负权边承诺：Dijkstra 框架要求非负权；若输入可能有负权边，必须作为额外的输入承诺单独说明，否则算法不保证正确。

5.2 $s$--$t$ 连通性的 span program 图像¶

连通性还有另一种截然不同的量子解释，它不经过 Borůvka，而是直接把问题写成一个 span program。框架细节超出本课范围，但 witness 结构非常直观，值得一看。

把每条可能的边 $(u,v)$ 对应一个由输入位 $A_{uv}$ 控制的向量。Span program 的判定规则是：目标向量落在"可用向量"的张成空间内当且仅当 $s$ 与 $t$ 连通。两种情形的证书分别是：

正 witness（$s,t$ 连通时）：取一条 $s$--$t$ 路径，沿路径的每条边放一单位流。路径流是"目标在张成空间内"的显式线性组合系数，其 witness size 与路径长度相关——更一般地，最优正 witness 是 $s$--$t$ 之间的单位电流，witness size 就是有效电阻 $R_{s,t}$（见本章电阻一课）。
负 witness（$s,t$ 不连通时）：取一个顶点势函数 $\varphi$：在 $s$ 的连通分量上取 0、在 $t$ 上取 1，它在每条存在的边上两端相等（即沿着边没有"电压差"），只在跨割的潜在边上有落差。割势函数证明目标不在张成空间内，其规模与割的参数相关。

Span program 的通用编译定理说：查询复杂度由正、负 witness size 的几何平均决定。代入最坏情形的路径/割参数，通用上界仍是约 $n^{3/2}$——与 Borůvka 路线殊途同归；但在特定图承诺下（例如承诺 $s$--$t$ 间有效电阻小、或割大），witness size 更小，复杂度可以做细，这是 span program 路线独有的优势。

此外，span program 的求值可以通过"两个反射的复合 + 相位检测"实现（这正是第 3 章相位估计与第 6 章量子行走的接口）：双反射相位检测把整个算法的空间压到 $O(\operatorname{polylog} n)$ 个量子比特，并保持近似同阶的门时间。与需要维护 $n$ 个顶点标签的 Borůvka 实现相比，这是空间上的实质性改进。

6. 稀疏性质与 minor-closed 性质¶

6.1 定义与例子¶

一个图性质（即一族在同构下封闭的图）称为稀疏的 (sparse)，如果所有满足该性质的 $n$ 顶点图都只有 $O(n)$ 条边——即边数被钉死在线性量级。许多自然的性质是稀疏的，其来源往往是 minor-closed：称性质 $\mathcal P$ 是 minor-closed 的，若 $G\in\mathcal P$ 蕴含 $G$ 的所有 minor（通过删边、缩边得到的图）也在 $\mathcal P$ 中。典型的 minor-closed 稀疏性质：

平面性（平面图最多 $3n-6$ 条边）；
森林/无圈性（最多 $n-1$ 条边）；
排除固定长度的路径 minor（路径长度受控时边数线性）。

稀疏性为量子算法提供了第 1.2 节所说的"额外承诺"：yes 实例的边只有 $O(n)$ 条，这改变了复杂度景观。

6.2 量子算法策略¶

对稀疏、minor-closed 性质，量子算法的通用策略分三步：

稠密度检查：先用 Grover 在 $\binom n2$ 个 entry 中搜索"边"，估计边数；若边数远超 $O(n)$，输入直接是否实例（因为 yes 图承诺稀疏），拒绝。这一步约 $O(n)$ 到 $O(n^{3/2})$ 查询。
局部证书搜索：若输入保持稀疏，minor-closed 性质往往有有限的 forbidden minor/subgraph 列表（Robertson--Seymour 定理保证有限 forbidden minor 列表的存在；对 forbidden subgraph 可描述的性质列表更具体），算法用 quantum walk 在顶点子集上行走、缓存已查询的诱导子图，搜索这些局部证书。其成本由证书结构决定，见第 7--8 节的参数化方法。
无法用有限 forbidden subgraph 描述的性质：对这类性质（包括许多自然的 minor-closed 性质），adversary 方法给出 $\Omega(n^{3/2})$ 下界，与 Borůvka 型上界闭合，复杂度为 $\Theta(n^{3/2})$。

6.3 一处文献勘误¶

这里应纠正 Quantum Algorithm Zoo 当前文字中的指数笔误：Zoo 相关条目把多数 minor-closed 性质的复杂度写成了 $\Theta(n^{2/3})$，但 Childs--Kothari 原论文在邻接矩阵、$n$ 顶点口径下给出的是

\[ \Theta(n^{3/2}). \]

为什么 $n^{2/3}$ 一定不对？一个尺度论证：$n^{2/3}$ 甚至小于读取一个顶点的整行邻接信息的自然尺度——量子地"在一个顶点的 $n$ 个潜在邻居中找一条边"就需要 $\Theta(\sqrt n)$ 次查询，而 $\sqrt n\gg n^{2/3}$。任何需要逐顶点探测邻接信息的图性质判定，复杂度都不可能低于 $\sqrt n$ 量级，更不可能低到 $n^{2/3}$。该指数也与原论文摘要明确陈述的 $n^{3/2}$ 不符，应属录入笔误。

同时要注意区分：可由有限 forbidden subgraph 列表描述的性质（注意是 subgraph 而非 minor，例如"不含三角形"）是另一类，其复杂度为 $o(n^{3/2})$——严格小于 $n^{3/2}$，具体指数依 forbidden graph 的结构（顶点数、边数、vertex cover 等）而定。这正是第 7、8 节的主题。

7. 三角形查找：从三重 Grover 到 learning graph¶

7.1 朴素基线¶

三角形检测：判定 $G$ 是否含三个两两相邻的顶点 $(u,v,w)$。

最直接的量子算法：遍历所有三元组，用 Grover 搜索。三元组共 $\binom n3=\frac{n(n-1)(n-2)}{6}=\Theta(n^3)$ 个；检查一个三元组是 3 次边查询（检查 $(u,v),(v,w),(u,w)$ 三条边，常数成本）。由 Grover：

\[ O\!\left(\sqrt{n^3}\right)=O(n^{3/2}). \]

这个基线与连通性/MST 同阶，但它不是最优的。低效之处在于：不同的候选三角形共享大量的边——$(u,v,w)$ 和 $(u,v,w')$ 需要同一条边 $(u,v)$——而三重 Grover 把每次边查询当作一次性的，查完即弃。改进的全部来源就是缓存并复用已查询的边。

7.2 缓存诱导子图的量子行走¶

量子行走/learning graph 路线的核心数据结构是一个 $r$ 元顶点子集 $S$ 及其完全查询过的诱导子图（即 $S$ 内部全部 $\binom r2$ 条边的查询结果）。行走在这个"缓存态"上进行，四步结构如下（对应原文的四步，此处把每步的成本来源讲清）：

Setup（建立缓存）：随机选 $r$ 个顶点，查询其诱导子图的全部边，成本 $$S_{\text{setup}}=O(r^2).$$
Update（行走一步）：把 $S$ 中一个顶点替换为外部顶点。诱导子图中只有与这个顶点相关的 $r-1$ 条边发生变化，故更新缓存只需 $$U_{\text{update}}=O(r).$$ 行走的"图"是 Johnson 图 $J(n,r)$：顶点为 $r$ 元子集，相邻子集差一个顶点；其谱隙为 $\delta=\Theta(1/r)$（$r\le n/2$ 时）。谱隙决定"把缓存有效地换成一个随机新缓存"需要多少步：由量子行走的标准分析，这贡献一个 $1/\sqrt\delta=\sqrt r$ 的因子。
Check（检查）：若缓存的诱导子图中已含三角形，直接接受（免费）。否则，固定的三角形若恰有两个顶点 $u,v\in S$，则第三个顶点 $w$ 在外部 $n-r$ 个顶点中，且需满足 $(u,w),(v,w)$ 都是边。对每个"缓存内边" $(u,v)$ 做一次对外部顶点的嵌套 Grover 搜索，单条边的检查成本 $O(\sqrt n)$。
命中概率：一个固定的三角形，其某条指定边的两个端点都落在随机 $r$ 元子集中的概率为 $\Theta((r/n)^2)$。于是缓存"命中"三角形的比例为 $\varepsilon=\Theta((r/n)^2)$，由振幅放大/行走的标准分析，到达一个命中缓存需要 $1/\sqrt\varepsilon=n/r$ 量级的行走步数。

7.3 参数平衡：简化模型的完整推导¶

把四步代入量子行走搜索的标准成本公式（setup + 步数 ×（check + 扩散 × update））：

\[ T(r)=\underbrace{r^2}_{\text{setup}} +\underbrace{\frac{n}{r}}_{1/\sqrt\varepsilon} \left(\underbrace{\sqrt n}_{\text{check}} +\underbrace{\sqrt r\cdot r}_{(1/\sqrt\delta)\,U_{\text{update}}}\right) =r^2+\frac{n^{3/2}}{r}+n\,r^{1/2}. \]

现在求 $r$ 使 $T(r)$ 最小。三项随 $r$ 单调性不同（setup 增、中间项减、末项增），极小值在主导项同阶处取得。试令第一项与第三项同阶：

\[ r^2=n\,r^{1/2} \;\Longleftrightarrow\; r^{3/2}=n \;\Longleftrightarrow\; r=n^{2/3}. \]

代回验证此时三项的量级：

\[ r^2=n^{4/3},\qquad \frac{n^{3/2}}{r}=\frac{n^{3/2}}{n^{2/3}}=n^{5/6},\qquad n\,r^{1/2}=n\cdot n^{1/3}=n^{4/3}. \]

中间项 $n^{5/6}$ 是低阶项，确实不影响平衡（这验证了"令第一、三项同阶"是自洽的选择），故

\[ T(n^{2/3})=O(n^{4/3}). \]

这就是均匀权重量子行走给出的 $O(n^{4/3})$，已严格优于三重 Grover 的 $O(n^{3/2})$。改进的机制在公式里看得很清楚：$r^2$ 条缓存边被 $n/r$ 步、每步检查 $O(\sqrt n)$ 个外部顶点反复复用，平均每个候选三角形分摊的查询远低于 3。

7.4 从均匀行走到 learning graph：记录的 $O(n^{5/4})$¶

上面的简化模型对所有缓存边一视同仁（均匀流）。learning graph 框架把"查询哪些边、以什么振幅查询"本身变成优化变量：给更可能属于三角形的边分配更大的查询权重（非均匀流），进一步压缩 witness 规模。经过扩展 learning graph（extended learning graph）的非均匀流优化，Zoo 快照记录的查询上界为

\[ O(n^{5/4}). \]

这个界限的完整推导需要 learning graph 的对偶规划技术，超出本课范围；但要强调原文已标注的一点：$O(n^{5/4})$ 不是"把三个 edge queries 视为常数后直接 Grover"能得到的——那条路只有 $O(n^{3/2})$。从 $n^{3/2}$ 到 $n^{4/3}$ 再到 $n^{5/4}$，每一步改进都来自对"候选三角形之间共享边查询"这一结构越来越精细的利用。

最后是一个模型依赖的保留条款：上述参数平衡针对稠密、无承诺的输入。稀疏图（第 6 节）、检测固定的更大子图 $H$（第 8 节）、以及 3-uniform hypergraph 中的三元组检测，各自的最优 $r$、缓存结构与最终指数都不同，不能直接套用本节的数字。

8. 固定子图与 1-certificate 复杂度¶

把三角形换成任意固定图 $H$（$H$ 与 $n$ 无关，例如 $K_4$、5-圈、Petersen 图），问题变为：判定 $G$ 是否含一个与 $H$ 同构的子图。

证书的视角。yes 实例的证书（1-certificate）就是 $H$ 在 $G$ 中的一个拷贝，即常数条边的存在性。这解释了为什么这类性质能进入 $o(n^{3/2})$ 的区间：与连通性不同，判定不需要"全局"信息，一个常数大小的局部结构就足够。Span program 与 learning graph 可以按 $H$ 的精细结构参数设计流——常用的参数包括 $H$ 的 vertex cover 数 $\operatorname{vc}(H)$（覆盖所有边所需的最少顶点数）、最大度数与边数——典型策略是先加载高复用顶点（覆盖集中、与许多候选拷贝关联的顶点），再加载证书边。因此查询指数常写成这些图参数的函数，而不只是 $|V(H)|$ 的函数；三角形是 $H=K_3$、$\operatorname{vc}(H)=2$ 的特例。

稀疏承诺下的指数。若输入图被承诺为稀疏（yes 与 no 实例都只有 $O(n)$ 条边，或至少边数受控），找到 $H$ 的复杂度可由形如

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

的界控制（$\widetilde O$ 隐藏对数因子）。对三角形 $\operatorname{vc}(K_3)=2$，指数为 $3/2-1/3=7/6$。注意这里的机制：稀疏承诺让"以某顶点为中心的候选结构"数量受控，缓存与嵌套搜索的平衡点随之移动。没有稀疏承诺时不能使用同一公式——第 7 节稠密情形的记录是 $O(n^{5/4})$ 而非 $\widetilde O(n^{7/6})$，两个公式适用的输入模型不同，混用是本主题最常见的错误。

Tree-minor 检测则是另一幅图景："包含某个固定的树作为 minor"可以用 span program 表述，其 witness 是路径/流结构（与第 5.2 节连通性 witness 同源），而不是枚举所有可能的映射 $\varphi:V(H)\to V(G)$——后者有 $n^{|V(H)|}$ 个候选，直接搜索毫无优势。这再次说明：在图问题上，witness 的代数结构决定量子加速的形状，而不是候选空间的朴素大小。

9. 查询复杂度之外：门、空间与输出¶

本课到此为止只数查询。把算法落到真实资源上，有三个必须单独记账的项目。

Oracle 的实现对成本的影响。邻接矩阵 oracle 允许在叠加中访问任意边，这是一个强假设。若图实际以压缩的 edge list 存储，模拟一次 $A_{uv}$ 查询可能需要一次字典查找（"$(u,v)$ 是否在列表中"），其成本与列表的存储结构有关，会乘到所有查询上界上。反过来，邻接表 oracle（输入顶点 $u$ 和序号 $i$，返回 $u$ 的第 $i$ 个邻居）能直接枚举邻居，却不擅长回答"$(u,v)$ 是不是非边"这类任意点对查询——下一课会看到，同一批图问题的复杂度在这个模型下会改变。

输出规模的下界。MST 的输出是 $n-1$ 条边，因此无论查询多少次，仅写出输出就需要 $\Omega(n)$ 时间。这不妨碍 $\Theta(n^{3/2})$ 的查询复杂度结论，但提醒我们：查询复杂度不是时间复杂度。

辅助结构的门成本。Borůvka 的量子实现需要可逆的并查集（维护分量标签）、learning graph 需要缓存边的可逆读写与 reflection 算子的合成，span program 求值需要相位估计的精度开销。这些都贡献 $\operatorname{polylog}$ 量级的门因子——不改变查询指数，但在比较"谁真正更快"时必须计入。相比之下，三角形判定只输出一个比特，是最纯的查询复杂度问题；而 MST 类构造性问题总是查询与门成本并重的。

10. 小结¶

邻接矩阵模型含 $\binom n2=\Theta(n^2)$ 个潜在 entry，经典最坏情形必须读完整张表；量子搜索把许多图问题降到 $n^{3/2}$ 尺度。
Borůvka 每轮为各分量量子查找最轻出边，Cauchy--Schwarz 给出单轮 $O(n\sqrt c)$，分量数减半的几何级数求和得到 $O(n^{3/2})$；下界用精细的 adversary/search 归约匹配，连通性与 MST 均为 $\Theta(n^{3/2})$，查询最优。
Span program 用路径流（正 witness，规模关联路径长度/有效电阻）与割势（负 witness）表示 connectivity 与 minor 检测，双反射求值把空间压到 polylog 量子比特。
Minor-closed 性质多数为 $\Theta(n^{3/2})$（注意 Zoo 条目 $n^{2/3}$ 系笔误）；可由有限 forbidden subgraph 描述的性质为 $o(n^{3/2})$。
三角形检测：三重 Grover 基线 $O(n^{3/2})$；缓存 $r$ 点诱导子图的均匀行走给 $O(n^{4/3})$（平衡 $r^2$ 与 $nr^{1/2}$ 得 $r=n^{2/3}$）；扩展 learning graph 的非均匀流进一步优化到 $O(n^{5/4})$。改进的本质是共享边查询的复用。
固定子图 $H$ 的指数由 $\operatorname{vc}(H)$ 等结构参数控制；稀疏承诺下的公式（如 $\widetilde O(n^{3/2-1/(\operatorname{vc}(H)+1)})$）不能套用到稠密情形。

练习题¶

练习 1【邻接矩阵 oracle 与查询模型】（→ 1.1 节）

基础：写出无权邻接矩阵 oracle $O_G|u,v,z\rangle=|u,v,z\oplus A_{uv}\rangle$ 的定义；指出 $n$ 顶点简单无向图的邻接矩阵有多少个独立 entry，并说明取 $|z\rangle=|-\rangle$ 时如何由它得到相位 oracle。
进阶：在"图以邻接表存储"的经典世界里，判定连通性只需读 $O(n+m)$ 个条目。解释为什么在 entry-query 模型中"先花 $O(m)$ 次查询确认图只有 $m$ 条边"不可行：确认其余位置全为 $0$ 需要多少次查询？

提示：未被查询过的位置既可能是 $0$ 也可能是 $1$，排除它们只能逐个查询。

练习 2【经典基准与对抗者下界】（→ 1.3 节）

基础：复述两半划分的对抗者策略，说明在最后一对跨半 entry 被查询之前算法为何无法停机，并计算它被迫查询的跨半 entry 总数。
进阶：写出在"只剩最后一对跨半 entry 未查询"时，与算法已见的全部回答相容的两张图（一张连通、一张不连通），并说明从确定性论证推广到随机算法为什么需要 Yao 原理。

提示：两张图只在那个尚未查询的位置上不同。

练习 3【单轮量子成本与几何级数】（→ 3.2 节）

基础：完整推导各轮成本：从单分量候选数 $|C_j|(n-|C_j|)\le n|C_j|$ 出发，经 Cauchy--Schwarz 得到单轮 $O(n\sqrt c)$，再对 $c_t\le n/2^t$ 求几何级数；计算常数 $\frac{1}{1-2^{-1/2}}$ 的数值，并说明对轮数上界 $\lceil\log_2 n\rceil$ 的依赖为何最终消失在大 $O$ 里。
基础：复核 3.4 节的 $n=4$ 小例子：写出两轮结束后的 MST 及其总权值，验证两轮的查询成本估计都恰好等于上界 $n\sqrt c$，并解释两轮都取等的原因。
进阶：证明单轮上界 $O(n\sqrt c)$ 在各分量等大时对 Cauchy--Schwarz 取等号；再构造分量大小悬殊的例子（例如一个 $n-1$ 顶点分量加一个单点），计算该轮的实际最小值查找总成本，说明它与 $n\sqrt c$ 的差距。

提示：$\sqrt{n(n-1)}<n$，而 $c=2$ 时的上界是 $n\sqrt2$。

练习 4【匹配下界与查询最优性】（→ 第 4 节）

基础：把"两个各含 $n/2$ 顶点的团之间是否存在跨团边"编码为对 $\frac{n^2}{4}$ 个位置的 OR，说明连通性判定为什么蕴含解这个 OR，写出由此得到的 $\Omega(n)$ 下界，并指出它与上界 $O(n^{3/2})$ 之间相差的 $\sqrt n$ 因子来自哪里。
进阶：解释精细下界构造为什么要让每一轮的每个分量都面对一个大小 $\Theta(n|C_j|)$ 的独立搜索实例、并让各分量保持均匀，从而对分量、对轮次求和后复现上界分析中的同一个几何级数，闭合为 $\Theta(n^{3/2})$。

提示：联系 3.2 节 Cauchy--Schwarz 的取等条件——上界最坏与下界最难都发生在各分量等大时。

练习 5【Span program 见证结构】（→ 5.2 节）

基础：写出 $s$--$t$ 连通时正 witness 的构造（沿一条 $s$--$t$ 路径的每条边放一单位流），并说明把"单位流"换成"单位电流"后，正 witness size 对应图中的哪个经典量。
进阶：取 $s$--$t$ 连通性实例：5 个顶点排成一条路径 $s=v_1-v_2-v_3-v_4-v_5=t$（无其他边）。写出正 witness（路径流）与"假想断边"情形下的负 witness（割势函数），并指出各自的规模由什么参数决定。

提示：割势函数在断边一侧的连通分量上取 $0$、另一侧取 $1$。

练习 6【稀疏与 minor-closed 性质】（→ 6.1 节）

基础：给出稀疏性质与 minor-closed 性质的定义并各举两个例子；写出平面图与森林的边数上界。
进阶：解释为什么 Zoo 中 $n^{2/3}$ 的 minor-closed 指数与 Childs--Kothari 原论文的 $n^{3/2}$ 冲突：用量子地读取单个顶点邻接行需要 $\Theta(\sqrt n)$ 次查询这一事实，论证任何需要逐顶点探测邻接信息的图性质判定都不可能是 $o(\sqrt n)$，并指出判定指数正误的最终依据。

提示：$\Omega(\sqrt n)$ 的尺度论证与"排除 $n^{2/3}$"是两个强度不同的结论，勘误以原论文的明确陈述为准。

练习 7【三角形与固定子图检测】（→ 7.1 节）

基础：推导三重 Grover 基线：候选三元组共 $\binom n3=\Theta(n^3)$ 个、检查一个三元组需 3 次边查询，由 Grover 得 $O(n^{3/2})$；并指出这一做法的浪费出在哪里。
进阶：对 7.3 节的成本函数 $T(r)=r^2+\frac{n^{3/2}}{r}+nr^{1/2}$：（a）验证 $r=n^{2/3}$ 使第一、三项同阶且中间项为低阶；（b）若改为令第一项与中间项同阶，求出对应的 $r$ 与总成本，并与（a）的总成本比较大小；（c）解释为什么不能取 $r=\Theta(n)$。

提示：（b）中令 $r=n^a$ 比较三项的指数，注意第三项何时成为主导。

练习 8【查询复杂度之外】（→ 第 9 节）

基础：分别说出邻接矩阵 oracle 与邻接表 oracle 擅长与不擅长的查询类型；并说明为什么 MST 的输出本身就迫使任何算法的时间复杂度至少为 $\Omega(n)$。
进阶：论证即使未来发现查询复杂度为 $O(n)$ 的 MST 算法，其时间复杂度仍不可能低于 $\Omega(n)$；再结合第 9 节讨论"查询最优"与"实际可用"之间的区别，并给出你认为最接近"纯查询复杂度问题"的图问题及理由。

提示：比较三角形判定（输出 1 个比特）与 MST（输出 $n-1$ 条边）的输出规模。

参考文献与 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 与稀疏图算法。