邻接矩阵模型图算法

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

这个问题之所以值得认真对待，有三个原因。第一，它是”量子平方加速”最干净的样板：许多图性质的经典查询复杂度是 $\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 搜索与振幅放大、相位估计，以及”量子行走 = 两个反射的复合”这一基本图像。我们会用到它们，但不重新推导。

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

1.1 问题与 oracle 的严格定义

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

$$A_{uv}=\{\begin{array}{ll}1,& \{u,v\}\in E,\\ 0,& \text{否则}.\end{array}$$

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

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

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

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

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

$$O_G|u,v,z⟩=|u,v,z\oplus w(u,v)⟩,$$

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

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

请注意 oracle 的语义：查询任意一对 $(u,v)$ 的成本完全相同，不论真实图是稀疏还是稠密。 这一点初看显然，实际上决定了整课的难度结构。想象图只有 $m\ll n^2$ 条边——经典算法如果用邻接表存储，只需要扫过 $2m$ 个条目；但在邻接矩阵 oracle 下，“稀疏”这个事实本身也要靠查询去发现：你不知道哪些位置是 1，就仍然要面对全部 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 个潜在 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 搜索与最小值查找

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

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/\mathrm{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^{\prime }$ 离开 $C$（从 $C$ 出发的环必须回到 $C$）；由 $e$ 的最轻性 $w(e)\le w(e^{\prime })$，于是 $T-e^{\prime }+e$ 仍是生成树且权值不增。把这条性质应用到每个分量，就得到 Borůvka 每轮加入的边全部安全。

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

3.2 单轮的量子成本

进入量子部分。设当前某一轮的分量为 $C_1,\dots ,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 不等式 $({\sum }_{j}1\cdot \sqrt{|C_j|}{)}^2\le ({\sum }_j{1}^2\left)\right({\sum }_j|C_j|)$，即

$${\left(\sum _{j=1}^c\sqrt{|C_j|}\right)}^2\le c\cdot \sum _{j=1}^c|C_j|=cn,$$

其中第二个等号是因为各分量互不相交且覆盖全部 $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,\dots$）。把单轮成本代入并求和：

$$\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}{\sqrt{2}}}\approx \mathrm{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,w_{34}=1,w_{13}=5,w_{14}=6,w_{23}=7,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\sqrt{2}\approx 2.83$，两个分量共 $4\sqrt{2}\approx 5.66$；上界 $n\sqrt{c}=4\sqrt{2}\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}\mathrm{polylog}n\right)$$

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

1. 权值比较：键值是实数/整数权值，比较与加法必须精确到足够位宽，这贡献对数因子；
2. 优先结构：动态键值需要可逆的数据结构支持，查询复杂度不变，但门复杂度会多出 $\mathrm{polylog}$ 因子；
3. 负权边承诺：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$ 不连通时）：取一个顶点势函数 $\phi$：在 $s$ 的连通分量上取 0、在 $t$ 上取 1，它在每条存在的边上两端相等（即沿着边没有”电压差”），只在跨割的潜在边上有落差。割势函数证明目标不在张成空间内，其规模与割的参数相关。

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

此外，span program 的求值可以通过”两个反射的复合 + 相位检测”实现（这正是相位估计与量子行走的接口）：双反射相位检测把整个算法的空间压到 $O(\mathrm{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 性质，量子算法的通用策略分三步：

1. 稠密度检查：先用 Grover 在 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 个 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

7.1 朴素基线

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

最直接的量子算法：遍历所有三元组，用 Grover 搜索。三元组共 $\left(\genfrac{}{}{0ex}{}{n}{3}\right)=\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^{\prime })$ 需要同一条边 $(u,v)$——而三重 Grover 把每次边查询当作一次性的，查完即弃。改进的全部来源就是缓存并复用已查询的边。

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

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

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)$。于是缓存”命中”三角形的比例为 $\epsilon =\Theta ((r/n{)}^2)$，由振幅放大/行走的标准分析，到达一个命中缓存需要 $1/\sqrt{\epsilon }=n/r$ 量级的行走步数。

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

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

$$T(r)=\underset{\text{setup}}{\underbrace{r^2}}+\underset{1/\sqrt{\epsilon }}{\underbrace{\frac{n}{r}}}\left(\underset{\text{check}}{\underbrace{\sqrt{n}}}+\underset{(1/\sqrt{\delta })U_{\text{update}}}{\underbrace{\sqrt{r}\cdot r}}\right)=r^2+\frac{n^{3/2}}{r}+n{r}^{1/2}.$$

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

$$r^2=n{r}^{1/2}⟺r^{3/2}=n⟺r=n^{2/3}.$$

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

$$r^2=n^{4/3},\frac{n^{3/2}}{r}=\frac{n^{3/2}}{n^{2/3}}=n^{5/6},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 数 $\mathrm{vc}(H)$（覆盖所有边所需的最少顶点数）、最大度数与边数——典型策略是先加载高复用顶点（覆盖集中、与许多候选拷贝关联的顶点），再加载证书边。因此查询指数常写成这些图参数的函数，而不只是 $|V(H)|$ 的函数；三角形是 $H=K_3$、$\mathrm{vc}(H)=2$ 的特例。

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

$$\tilde{O}\left(n^{3/2-1/(\mathrm{vc}(H)+1)}\right)$$

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

Tree-minor 检测则是另一幅图景：“包含某个固定的树作为 minor”可以用 span program 表述，其 witness 是路径/流结构（与第 5.2 节连通性 witness 同源），而不是枚举所有可能的映射 $\phi :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 求值需要相位估计的精度开销。这些都贡献 $\mathrm{polylog}$ 量级的门因子——不改变查询指数，但在比较”谁真正更快”时必须计入。相比之下，三角形判定只输出一个比特，是最纯的查询复杂度问题；而 MST 类构造性问题总是查询与门成本并重的。

10. 小结与习题

小结：

• 邻接矩阵模型含 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\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$ 与 $n{r}^{1/2}$ 得 $r=n^{2/3}$）；扩展 learning graph 的非均匀流进一步优化到 $O(n^{5/4})$。改进的本质是共享边查询的复用。
• 固定子图 $H$ 的指数由 $\mathrm{vc}(H)$ 等结构参数控制；稀疏承诺下的公式（如 $\tilde{O}(n^{3/2-1/(\mathrm{vc}(H)+1)})$）不能套用到稠密情形。

习题：

1.（推导复核）完整推导 Borůvka 量子算法各轮成本：从单分量候选数 $|C|(n-|C|)\le n|C|$ 出发，经 Cauchy—Schwarz 到单轮 $O(n\sqrt{c})$，再对 $c_t=n/2^t$ 求几何级数。计算常数 $\frac{1}{1-2^{-1/2}}$ 的数值，并说明为什么对 $n$ 的轮数上界 $\lceil {\log }_{2}n\rceil$ 的依赖最终消失在大 $O$ 里。 2.（紧性分析）证明单轮成本上界 $O(n\sqrt{c})$ 在各分量等大时对 Cauchy—Schwarz 取等号。构造一个分量大小悬殊的例子（例如一个 $n-1$ 顶点分量加一个单点），计算该轮的实际最小值查找总成本，说明它与 $n\sqrt{c}$ 的差距。 3.（witness 构造）取 $s$—$t$ 连通性实例：5 个顶点排成一条路径 $s=v_1-v_2-v_3-v_4-v_5=t$（无其他边）。写出第 5.2 节意义下的一个正 witness（路径流）与一个”假想断边”情形下的负 witness（割势函数），并指出各自的规模由什么参数决定。 4.（文献辨析）解释为什么 Zoo 中 $n^{2/3}$ 的 minor-closed 指数与 Childs—Kothari 原论文的 $n^{3/2}$ 冲突：用量子地读取单个顶点邻接行需要 $\Theta (\sqrt{n})$ 次查询这一事实，论证任何 $o(\sqrt{n})$ 的图性质判定算法都不可能在邻接矩阵模型中存在。 5.（参数平衡）对第 7.3 节的成本函数 $T(r)=r^2+\frac{n^{3/2}}{r}+n{r}^{1/2}$：（a）验证 $r=n^{2/3}$ 使第一、三项同阶且中间项为低阶；（b）若改为令第一项与中间项同阶，求出对应的 $r$ 与总成本，说明它不如 $n^{4/3}$；（c）解释为什么不能取 $r=\Theta (n)$（提示：谱隙 $\delta =\Theta (1/r)$ 的成立范围与”随机替换顶点”的语义）。 6.（模型讨论）MST 输出 $n-1$ 条边。论证：即使未来发现查询复杂度为 $O(n)$ 的 MST 算法，其时间复杂度仍不可能低于 $\Omega (n)$；再结合第 9 节，讨论”查询最优”与”实际可用”之间的区别。你认为哪个图问题最接近”纯查询复杂度问题”？

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

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch12-quantum-graphs/adjacency-matrix-properties
• 内容遵循 CC BY-NC-SA 4.0 许可协议