# 邻接矩阵模型图算法：连通性、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 章）。我们会用到它们，但不重新推导。 :::{admonition} 本课知识点 :class: tip 1. **[邻接矩阵 oracle 与查询模型](#adjacency-oracle)**——写出无权与加权邻接矩阵 oracle 的作用方式，并解释为什么图稀疏不会自动降低 entry-query 模型的查询成本。 2. **[经典基准与对抗者下界](#classical-adversary)**——复述两半划分的对抗者策略，证明连通性判定的经典查询复杂度为 $\Theta(n^2)$，并说明量子下界为何需要更精细的构造。 3. **[单轮量子成本与几何级数](#round-cost-geometric-series)**——推导单分量成本 $O(\sqrt{n|C_j|})$，用 Cauchy--Schwarz 证明单轮总成本 $O(n\sqrt c)$，再对分量数减半的几何级数求和得到 $O(n^{3/2})$。 4. **[匹配下界与查询最优性](#matching-lower-bound)**——解释朴素搜索归约只给出 $\Omega(n)$ 的原因与"批量复用"机制，并说明精细 adversary 归约如何复现同一几何级数闭合为 $\Theta(n^{3/2})$。 5. **[Span program 见证结构](#span-program-witnesses)**——写出 $s$--$t$ 连通性的正 witness（路径流）与负 witness（割势）构造，并解释查询复杂度为何由两种 witness size 的几何平均决定。 6. **[稀疏与 minor-closed 性质](#sparse-minor-closed)**——解释稀疏性与 minor-closed 性质的定义和三步算法策略，并辨析 Zoo 条目 $n^{2/3}$ 与原论文 $n^{3/2}$ 的指数冲突。 7. **[三角形与固定子图检测](#triangle-subgraph)**——计算三重 Grover 基线 $O(n^{3/2})$，推导缓存式量子行走的参数平衡 $r=n^{2/3}$ 得到 $O(n^{4/3})$，并说明向 $O(n^{5/4})$ 的改进为何来自共享边查询的复用。 8. **[查询复杂度之外](#beyond-query)**——解释查询复杂度与时间、空间复杂度的区别，并论证 MST 的输出规模为何迫使任何算法的时间下界为 $\Omega(n)$。 ::: ## 1. 邻接矩阵 oracle 与复杂度尺度 (adjacency-oracle)= ### 1.1 问题与 oracle 的严格定义 设 $G=(V,E)$ 是一个 $n$ 顶点的简单无向图，$A$ 是它的 $n\times n$ **邻接矩阵 (adjacency matrix)**： $$ A_{uv}= \begin{cases} 1, & \{u,v\}\in E,\\ 0, & \text{否则}. \end{cases} $$ 因为图是无向的，$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)$ 进行。 (classical-adversary)= ### 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）维护一个**生成森林**：初始时每个顶点自成一个连通分量，算法分轮进行，每一轮做两件事： 1. 对当前每个连通分量 $C$，找一条**离开 $C$ 的最轻的边**（即一个端点在 $C$ 内、另一个端点在 $C$ 外的权值最小边）； 2. 把所有这些边加入森林，合并相应的分量。 当只剩一个分量时，森林就是一棵最小生成树。 **为什么这是对的（割性质）**：对任意顶点集 $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$ 轮结束。 (round-cost-geometric-series)= ### 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$。小例子确认了代数：当分量始终等大时，每轮都顶着上界走，几何衰减来自分量数的减半。 (matching-lower-bound)= ## 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) $$ 次查询可在邻接矩阵模型下求解单源最短路。引用这个结果时必须明确三个保留条款（原文已标注，此处解释）： 1. **权值比较**：键值是实数/整数权值，比较与加法必须精确到足够位宽，这贡献对数因子； 2. **优先结构**：动态键值需要可逆的数据结构支持，查询复杂度不变，但门复杂度会多出 $\operatorname{polylog}$ 因子； 3. **负权边承诺**：Dijkstra 框架要求非负权；若输入可能有负权边，必须作为额外的输入承诺单独说明，否则算法不保证正确。 (span-program-witnesses)= ### 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 性质 (sparse-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 性质，量子算法的通用策略分三步： 1. **稠密度检查**：先用 Grover 在 $\binom n2$ 个 entry 中搜索"边"，估计边数；若边数远超 $O(n)$，输入直接是否实例（因为 yes 图承诺稀疏），拒绝。这一步约 $O(n)$ 到 $O(n^{3/2})$ 查询。 2. **局部证书搜索**：若输入保持稀疏，minor-closed 性质往往有有限的 forbidden minor/subgraph 列表（Robertson--Seymour 定理保证有限 forbidden **minor** 列表的存在；对 forbidden **subgraph** 可描述的性质列表更具体），算法用 quantum walk 在顶点子集上行走、缓存已查询的诱导子图，搜索这些局部证书。其成本由证书结构决定，见第 7--8 节的参数化方法。 3. **无法用有限 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 (triangle-subgraph)= ### 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$ 条边的查询结果）。行走在这个"缓存态"上进行，四步结构如下（对应原文的四步，此处把每步的成本来源讲清）： 1. **Setup（建立缓存）**：随机选 $r$ 个顶点，查询其诱导子图的全部边，成本 $$S_{\text{setup}}=O(r^2).$$ 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$ 的因子。 3. **Check（检查）**：若缓存的诱导子图中已含三角形，直接接受（免费）。否则，固定的三角形若恰有两个顶点 $u,v\in S$，则第三个顶点 $w$ 在外部 $n-r$ 个顶点中，且需满足 $(u,w),(v,w)$ 都是边。对每个"缓存内边" $(u,v)$ 做一次对外部顶点的嵌套 Grover 搜索，单条边的检查成本 $O(\sqrt n)$。 4. **命中概率**：一个固定的三角形，其某条指定边的两个端点都落在随机 $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 的代数结构决定量子加速的形状**，而不是候选空间的朴素大小。 (beyond-query)= ## 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 节](#adjacency-oracle)） 1. 基础：写出无权邻接矩阵 oracle $O_G|u,v,z\rangle=|u,v,z\oplus A_{uv}\rangle$ 的定义；指出 $n$ 顶点简单无向图的邻接矩阵有多少个独立 entry，并说明取 $|z\rangle=|-\rangle$ 时如何由它得到相位 oracle。 2. 进阶：在"图以邻接表存储"的经典世界里，判定连通性只需读 $O(n+m)$ 个条目。解释为什么在 entry-query 模型中"先花 $O(m)$ 次查询确认图只有 $m$ 条边"不可行：确认其余位置全为 $0$ 需要多少次查询？ > 提示：未被查询过的位置既可能是 $0$ 也可能是 $1$，排除它们只能逐个查询。 **练习 2【经典基准与对抗者下界】**（→ [1.3 节](#classical-adversary)） 1. 基础：复述两半划分的对抗者策略，说明在最后一对跨半 entry 被查询之前算法为何无法停机，并计算它被迫查询的跨半 entry 总数。 2. 进阶：写出在"只剩最后一对跨半 entry 未查询"时，与算法已见的全部回答相容的两张图（一张连通、一张不连通），并说明从确定性论证推广到随机算法为什么需要 Yao 原理。 > 提示：两张图只在那个尚未查询的位置上不同。 **练习 3【单轮量子成本与几何级数】**（→ [3.2 节](#round-cost-geometric-series)） 1. 基础：完整推导各轮成本：从单分量候选数 $|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$ 里。 2. 基础：复核 3.4 节的 $n=4$ 小例子：写出两轮结束后的 MST 及其总权值，验证两轮的查询成本估计都恰好等于上界 $n\sqrt c$，并解释两轮都取等的原因。 3. 进阶：证明单轮上界 $O(n\sqrt c)$ 在各分量等大时对 Cauchy--Schwarz 取等号；再构造分量大小悬殊的例子（例如一个 $n-1$ 顶点分量加一个单点），计算该轮的实际最小值查找总成本，说明它与 $n\sqrt c$ 的差距。 > 提示：$\sqrt{n(n-1)} 提示：联系 3.2 节 Cauchy--Schwarz 的取等条件——上界最坏与下界最难都发生在各分量等大时。 **练习 5【Span program 见证结构】**（→ [5.2 节](#span-program-witnesses)） 1. 基础：写出 $s$--$t$ 连通时正 witness 的构造（沿一条 $s$--$t$ 路径的每条边放一单位流），并说明把"单位流"换成"单位电流"后，正 witness size 对应图中的哪个经典量。 2. 进阶：取 $s$--$t$ 连通性实例：5 个顶点排成一条路径 $s=v_1-v_2-v_3-v_4-v_5=t$（无其他边）。写出正 witness（路径流）与"假想断边"情形下的负 witness（割势函数），并指出各自的规模由什么参数决定。 > 提示：割势函数在断边一侧的连通分量上取 $0$、另一侧取 $1$。 **练习 6【稀疏与 minor-closed 性质】**（→ [6.1 节](#sparse-minor-closed)） 1. 基础：给出稀疏性质与 minor-closed 性质的定义并各举两个例子；写出平面图与森林的边数上界。 2. 进阶：解释为什么 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 节](#triangle-subgraph)） 1. 基础：推导三重 Grover 基线：候选三元组共 $\binom n3=\Theta(n^3)$ 个、检查一个三元组需 3 次边查询，由 Grover 得 $O(n^{3/2})$；并指出这一做法的浪费出在哪里。 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 节](#beyond-query)） 1. 基础：分别说出邻接矩阵 oracle 与邻接表 oracle 擅长与不擅长的查询类型；并说明为什么 MST 的输出本身就迫使任何算法的时间复杂度至少为 $\Omega(n)$。 2. 进阶：论证即使未来发现查询复杂度为 $O(n)$ 的 MST 算法，其时间复杂度仍不可能低于 $\Omega(n)$；再结合第 9 节讨论"查询最优"与"实际可用"之间的区别，并给出你认为最接近"纯查询复杂度问题"的图问题及理由。 > 提示：比较三角形判定（输出 1 个比特）与 MST（输出 $n-1$ 条边）的输出规模。 ## 参考文献与 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 与稀疏图算法。