# Graph Collision：已知图上的未知标记边搜索

给定一个完全已知的无向图 $G=(V,E)$，$|V|=n$，每个顶点带有一个未知标记

$$
x_v\in\{0,1\},
$$

并可通过 oracle 查询。Graph collision 问题要判断：是否存在一条边 $(u,v)\in E$，使得两个端点同时被标记，即 $x_u=x_v=1$。

这个问题的处境很微妙：**图结构是免费已知的，未知的只有顶点上的 $n$ 个比特**。它因此恰好卡在两个我们熟悉的问题之间——

- 它比 [Grover 无结构搜索](../ch03-algo-basics/grover.md) 难：目标不是"某个被标记的顶点"，而是"一对相邻的被标记顶点"，单次查询无法直接验证；
- 它比 [element distinctness](../ch11-query-complexity/collision-element-distinctness.md) 简单：那里的"碰撞关系"（两个函数值相等）是完全未知的，而这里的"碰撞关系"（邻接）就写在已知图 $G$ 里，可以随便翻阅。

本教程将看到：一般图上最优的通用算法用 Johnson 图量子行走达到 $O(n^{2/3})$ 次查询；而对特殊图族（接近完全图、随机稠密图、小 treewidth 图），可以利用独立集、非边数、treewidth 等结构参数把复杂度压到接近 $\sqrt n$。全文按"模型与下界 → 通用算法 → 结构参数 → 应用"的顺序推进，所有推导给出中间步骤。

**预备知识。** 我们默认读者已掌握 [Grover 算法](../ch03-algo-basics/grover.md) 与 [振幅放大](../ch03-algo-basics/amplitude-amplification.md)（特别是"$m$ 个条目中搜索一个标记条目需 $O(\sqrt m)$ 次查询"这一结论及其最优性），以及 [collision 与 element distinctness 教程](../ch11-query-complexity/collision-element-distinctness.md) 中建立的 Johnson 图量子行走框架；本教程直接引用该框架的成本公式，重点放在 graph collision 特有的参数计算与平衡上。

:::{admonition} 本课知识点
:class: tip

1. **[问题定义与查询模型](#query-model)**——能写出 graph collision 的判定条件与比特翻转 oracle 的作用，并说明"邻接免费、只计标记查询"的复杂度口径。
2. **[经典基线与朴素量子算法](#classical-naive-limits)**——能用对抗者论证说明经典算法最坏需要 $\Theta(n)$ 次查询，解释"对顶点 Grover"失败的原因，并计算"对边 Grover"的 $O(\sqrt m)$ 界及其在稠密图上的退化。
3. **[星图下界](#star-lower-bound)**——能证明在"中心被标记"承诺下星图子类上的 graph collision 等价于无结构搜索，从而推出一般图族的量子查询下界 $\Omega(\sqrt n)$。
4. **[Johnson 图量子行走与参数平衡](#johnson-walk-parameters)**——能为 graph collision 确定 MNRS 框架的 setup、update、check 与谱隙四个成本量，计算唯一碰撞边情形的 $\epsilon$，并平衡出 $r=n^{2/3}$、总成本 $O(n^{2/3})$。
5. **[非边数参数](#nonedge-parameter)**——能解释接近完全图时"先数标记、再排查例外对"的两步分解，说明 $\widetilde O(\sqrt n+\sqrt\ell)$ 界及其在完全图与稀疏图两个极端上的表现。
6. **[独立集总度参数](#alpha-star-parameter)**——能证明 no-instance 的标记集必为独立集，解释 $\alpha^*$ 的定义与 $O(\sqrt n+\sqrt{\alpha^*})$ 界，并推算随机稠密图上 $\alpha^*=O(n\log n)$。
7. **[独立数、treewidth 与按图择界](#alpha-treewidth-choice)**——能用 $O(\sqrt n\,\alpha^{1/6})$ 与 $O(\sqrt n\,t^{1/6})$ 两个界对具体图族做条件判断，并通过完全图、星图、路径三个图族的核算说明"按图择界"的原则。
8. **[triangle finding 归约](#triangle-finding-reduction)**——能写出固定候选顶点 $w$ 时 triangle 到 graph collision 的归约并验证充分、必要两个方向，说明逐个 $w$ 独立运行造成重复查询的原因。

:::

## 1. 问题的来源与动机

Graph collision 由 Magniez、Santha 与 Szegedy 在研究**三角形查找（triangle finding）**的量子算法时提出（Zoo 70）：他们发现，判断"图中是否存在三角形"可以分解为对每个候选顶点 $w$ 求解一个 graph collision 子问题，而这个子问题本身值得独立研究。

它的另一个近亲是 element distinctness。回忆 Ambainis 的 Johnson 图量子行走算法：在 $r$ 元子集上行走并缓存已查函数值，用 $\Theta(N^{2/3})$ 次查询判断列表中是否有重复元素。Graph collision 把"两个函数值相等"这一未知的等价关系，换成"两个顶点在已知图中相邻"这一已知的二元关系。一个自然的猜想是：已知关系应当让问题更容易。本教程的第 4–8 节会检验这个猜想——结论是"对一般图并不更容易（仍是 $n^{2/3}$），但对有结构的图确实更容易"。

这一方向的后续进展包括：利用补图非边数与独立集参数的 learning graph 上界（Zoo 161、172），Gavinsky 与 Ito 以"独立集总度"参数 $\alpha^*$ 给出的算法（Zoo 200，[arXiv:1204.1527](https://arxiv.org/abs/1204.1527)），以及 Ambainis 等关于 treewidth 等参数化上界的工作（Zoo 201）。本教程的复杂性论断与这些文献一致，并在正文标明哪些是严格推导、哪些只是启发式解释。

## 2. 模型、oracle 与两个朴素算法

(query-model)=
### 2.1 查询模型

标记通过标准的比特翻转 oracle 访问：

$$
O_x|v,z\rangle=|v,z\oplus x_v\rangle,
$$

其中 $v\in V$ 是顶点寄存器，$z\in\{0,1\}$ 是答案比特。一次查询得到**一个**顶点的标记。图的邻接关系**不计查询**：我们可以免费地把 $G$ 的邻接表写进经典控制电路，例如"枚举 $v$ 的所有邻居"或"判断 $(u,v)\in E$"都是零查询代价的经典操作。

我们要计的是 $O_x$ 的调用次数 $Q$，并要求算法对 yes-instance（存在碰撞边）与 no-instance（不存在碰撞边）都以至少 $2/3$ 的概率回答正确。

(classical-naive-limits)=
### 2.2 经典算法：$\Theta(n)$ 已是最优

经典确定性算法最坏情况必须查询全部 $n$ 个顶点：一个对抗者（adversary）可以在前 $n-1$ 次查询中都回答 $0$，此时未查询的那个顶点既可能让答案为 yes 也可能为 no（取决于图的结构），算法无法收场。随机化也只能把常数因子压到 $1/2$ 量级，最坏情况仍需 $\Theta(n)$ 次标记查询。这就是量子算法要击败的基线。

### 2.3 朴素量子算法一：对顶点做 Grover 为什么失败

第一反应是对顶点做 [Grover 搜索](../ch03-algo-basics/grover.md)，找一个被标记的顶点 $u$，再检查它的邻居。问题在于：找到 $u$ 只花了 $O(\sqrt n)$，但"检查 $u$ 的邻域里是否还有标记"本身又是一次搜索，代价 $O(\sqrt{\deg(u)})$；更麻烦的是，如果 $u$ 的邻域里没有标记，我们并不能排除**其他**被标记顶点之间存在碰撞边—— Grover 找到的只是"某个"标记顶点，而碰撞可能发生在任何一对之间。逐对排查退化回经典做法。这个失败说明：graph collision 的本质困难是**成对结构**，必须直接搜索"对"而不是"个"。

### 2.4 朴素量子算法二：对边做 Grover

既然目标是边，那就直接在所有边组成的集合上搜索。设 $|E|=m$，把每条边 $(u,v)$ 视为一个候选条目，"标记"谓词为 $x_u=x_v=1$；验证一个条目恰好需要两次 oracle 查询（查两个端点）。由振幅放大（见[振幅放大](../ch03-algo-basics/amplitude-amplification.md)），在 $m$ 个条目中搜索一个标记条目需要

$$
O(\sqrt m)
$$

轮迭代，每轮 $O(1)$ 次查询，总查询数 $O(\sqrt m)$。

这个界在稀疏图上是好的：若 $m=O(n)$（例如路径、树、平面图），则 $O(\sqrt m)=O(\sqrt n)$，与后文第 3 节的下界匹配，问题已经解决。**真正的困难在稠密图**：$m$ 可以达到 $\binom{n}{2}=\Theta(n^2)$，此时

$$
O(\sqrt m)=O(n),
$$

与经典算法一样坏，毫无优势。因此本教程的核心问题可以精确地表述为：**对稠密图，能否显著少于 $n$ 次查询？** 答案是肯定的，但需要把"已知的图结构"真正用起来，而不是仅仅把边列表当作无结构数据库。

(star-lower-bound)=
## 3. 下界：星图把 Grover 嵌入进来

在给出上界之前，先确定一般图族上任何算法都无法逾越的障碍。

取星图（star）$K_{1,n-1}$：一个中心顶点 $c$ 与 $n-1$ 个叶子 $\ell_1,\dots,\ell_{n-1}$，边集为 $\{(c,\ell_i)\}$。考虑如下**承诺子类**：承诺中心被标记，$x_c=1$。此时

$$
\text{collision 存在}\iff \text{某个叶子 } \ell_i \text{ 满足 } x_{\ell_i}=1.
$$

右边正是对 $n-1$ 个未知比特 $x_{\ell_1},\dots,x_{\ell_{n-1}}$ 求逻辑 OR，也就是 $N=n-1$ 的无结构搜索的判定版。由 Grover 搜索的最优性（[Grover 算法](../ch03-algo-basics/grover.md) 中引用的下界），任何量子算法都需要 $\Omega(\sqrt{n-1})=\Omega(\sqrt n)$ 次查询。

为什么可以加上"中心被标记"这个承诺？下界论证的标准逻辑是：**一个问题在某个输入子类上的下界，自动是整个问题的下界**——一个对所有输入都正确的通用算法，在这个子类上也必须正确。于是

$$
Q(\text{GraphCollision})=\Omega(\sqrt n)
$$

对一般图族成立。注意这个下界对所有"包含星图并允许该承诺"的图族都有效，包括"所有图"这个最大的图族。结合 2.2 节，经典与量子的差距至多是 $\Theta(n)$ 对 $O(\sqrt n)$ 级别的平方加速；后文的结构参数算法正是试图在各类图上逼近这个 $\sqrt n$。

(johnson-walk-parameters)=
## 4. 通用算法 I：Johnson 图量子行走框架

### 4.1 直觉：把 Grover 的"边列表"换成"缓存的顶点集"

2.4 节的失败在于：每条边的两个端点都要现查现用，$m$ 条边就是 $m$ 个独立的两查询条目。改进的想法来自 [collision 与 element distinctness 教程](../ch11-query-complexity/collision-element-distinctness.md)：与其在边上搜索，不如维护一个**顶点子集 $S$，把 $S$ 中所有顶点的标记一次性查好缓存起来**。一旦某个时刻 $S$ 同时包含某条碰撞边的两个端点，我们**不再花任何新查询**就能发现它——因为邻接关系免费、两个端点的标记都在缓存里。搜索空间从"$m$ 条边"变成"$\binom{n}{r}$ 个 $r$ 元子集"，而"当前子集是否包含碰撞"是零查询可读的标志。

为了让这个标志以量子方式被不断检查，我们把 $S$ 放进量子行走的态里。这就是 Magniez–Nayak–Roland–Santha（MNRS）框架的用武之地。

### 4.2 MNRS 量子行走的成本公式

我们在一个状态图（本教程取 Johnson 图）上做量子行走，每个状态 $S$ 附带一份缓存数据 $D(S)$。框架涉及四个量：

- **Setup 成本 $S_{\mathrm{set}}$**：制备所有状态的均匀叠加并装入数据，即制备 $\sum_S |S\rangle|D(S)\rangle$；
- **Update 成本 $U_{\mathrm{up}}$**：把行走的一步（$S$ 换成相邻的 $S'$）连同数据的更新一起可逆实现；
- **Check 成本 $C_{\mathrm{chk}}$**：给定 $(S,D(S))$，判断 $S$ 是否为"标记状态"（我们关心的好状态）；
- **标记比例 $\epsilon$ 与谱隙 $\delta$**：$\epsilon$ 是随机状态下为标记状态的概率下界（在最坏 yes-instance 下）；$\delta$ 是行走转移矩阵的谱隙，即最大与次大特征值之差，它衡量行走"扩散到全图"的速度。

MNRS 框架的结论（其推导见 [collision 与 element distinctness 教程](../ch11-query-complexity/collision-element-distinctness.md) 对 element distinctness 的完整分析，此处直接引用）是：判定"是否存在标记状态"的总查询成本为

$$
Q=O\!\left(
S_{\mathrm{set}}+\frac{1}{\sqrt{\epsilon}}
\left(\frac{1}{\sqrt{\delta}}\,U_{\mathrm{up}}+C_{\mathrm{chk}}\right)
\right).
$$

逐项解释每个因子的来源：

- $S_{\mathrm{set}}$ 只付一次：它是整个算法的入场费；
- 外层的 $1/\sqrt{\epsilon}$ 来自振幅放大：均匀叠加中只有 $\epsilon$ 比例的振幅落在好状态上，把它放大到常数概率需要 $O(1/\sqrt{\epsilon})$ 轮——这正是 Grover 迭代里 $\sin\theta\approx\sqrt{\epsilon}$ 的几何；
- 每一轮要实现的行走反射算子，本质上要求把行走算子的相位估计做到精度 $\sqrt{\delta}$（相位估计的精度换算为行走步数），每步行走花费 $U_{\mathrm{up}}$，故贡献 $U_{\mathrm{up}}/\sqrt{\delta}$；
- 同一轮里还要检查标志一次，花费 $C_{\mathrm{chk}}$。

### 4.3 Johnson 图 $J(n,r)$ 与本问题的四个参数

**Johnson 图** $J(n,r)$ 的顶点是所有 $r$ 元子集 $S\subset V$，两个子集相邻当且仅当它们恰好相差一个元素（$|S\triangle S'|=2$）。行走的一步就是"扔掉一个顶点、加入一个新顶点"。

对 graph collision，状态取为

$$
|S\rangle\otimes|D(S)\rangle,\qquad D(S)=\{(v,x_v):v\in S\},
$$

即 $r$ 元子集连同其中全部顶点标记的缓存。标记状态定义为：

$$
S \text{ 被标记}\iff \text{已知图 } G \text{ 的诱导子图 } G[S] \text{ 中存在两端都标记的边}.
$$

现在把四个参数逐一确定：

**Setup：$S_{\mathrm{set}}=r$。** 制备 $r$ 元子集的均匀叠加是免费的酉操作（制备 $\binom{n}{r}$ 个基矢的叠加不需要 oracle）；装入数据 $D(S)$ 需要对 $S$ 中每个顶点各查询一次，共 $r$ 次。

**Update：$U_{\mathrm{up}}=1$。** 一步行走把 $S$ 中的某个 $v$ 换成 $w$；缓存只需删除 $(v,x_v)$、加入 $(w,x_w)$——一次新查询（加上可逆擦除旧数据的标准技巧）。邻接信息免费，不构成查询。

**Check：$C_{\mathrm{chk}}=0$。** 判断 $G[S]$ 是否含全标记边，只需要翻缓存 $D(S)$ 和免费查 $G$ 的邻接表——零次新查询。这是 graph collision 与一般搜索问题的关键差别，也是"图已知"红利的兑现之处。值得强调的是"零查询"不等于"零电路"：检查要遍历 $S$ 内的顶点对并查邻接表，这是一段经典可逆电路，规模是 $r$ 的多项式；但在查询复杂度的口径下它完全免费。本教程与所引文献一致，只计 oracle 查询数。

**谱隙：$\delta=\Theta(1/r)$。** Johnson 图上"随机替换一个元素"链的谱隙为 $\Theta(1/r)$，这是 Johnson 图谱的经典事实（在 [collision 与 element distinctness 教程](../ch11-query-complexity/collision-element-distinctness.md) 中有同一事实的使用）。直觉上：一次随机替换只改变 $r$ 个元素中的一个，要让子集"忘掉"自己的初始状态大约需要 $r$ 步，混合时间的倒数正是 $\Theta(1/r)$ 量级。

## 5. 通用算法 II：$\epsilon$ 的计算与 $n^{2/3}$ 的平衡

### 5.1 最坏情形：恰好一条碰撞边

$\epsilon$ 的定义要求对**所有 yes-instance** 给出"随机 $r$ 元子集被标记"的概率下界。标记顶点越多、碰撞边越多，随机子集撞中碰撞的概率越大，所以最坏 yes-instance 是**恰好只有一条碰撞边 $(u^*,v^*)$、且其余顶点全部未标记**的情形。我们就在这个情形下精确计算 $\epsilon$；其他 yes-instance 的概率只会更大，故该值是合法下界。

### 5.2 逐步计算 $\epsilon$

$S$ 被标记，当且仅当 $u^*\in S$ 且 $v^*\in S$（其余 $r-2$ 个位置可以是任意顶点）。从 $n$ 个顶点中均匀随机取 $r$ 元子集，有利事件数是"先固定 $u^*,v^*$ 入选，再从剩下 $n-2$ 个顶点中任选 $r-2$ 个"：

$$
\epsilon=\frac{\binom{n-2}{r-2}}{\binom{n}{r}}.
$$

把组合数展开：

$$
\frac{\binom{n-2}{r-2}}{\binom{n}{r}}
=\frac{(n-2)!}{(r-2)!\,(n-r)!}\cdot\frac{r!\,(n-r)!}{n!}
=\frac{r!}{(r-2)!}\cdot\frac{(n-2)!}{n!}
=\frac{r(r-1)}{n(n-1)}.
$$

这里第一步代入了 $\binom{n}{k}=\frac{n!}{k!(n-k)!}$，第二步把阶乘配对约简（$(n-r)!$ 上下相消），第三步用 $\frac{r!}{(r-2)!}=r(r-1)$ 与 $\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}$。

当 $1\ll r\ll n$ 时，$r-1\approx r$、$n-1\approx n$，于是

$$
\epsilon=\frac{r(r-1)}{n(n-1)}=\Theta\!\left(\frac{r^2}{n^2}\right)=\Theta\!\left(\left(\frac{r}{n}\right)^2\right).
$$

这个结果有非常清楚的直觉：随机子集中每个顶点"中签"的比例是 $r/n$，而我们需要**两个指定的**顶点同时中签，两个近似独立的小概率事件相乘，给出 $(r/n)^2$。（严格地说两次抽取不独立，但上面的精确计算表明相关性只改变低阶项。）

**手算小例。** 取 $n=4$、$r=2$，图取路径 $1-2-3-4$，唯一碰撞边为 $(2,3)$。全部 $r$ 元子集共 $\binom{4}{2}=6$ 个，只有 $\{2,3\}$ 一个被标记，故 $\epsilon=1/6$；公式给出 $\frac{2\cdot1}{4\cdot3}=\frac{2}{12}=\frac16$，一致。此时渐近式 $(r/n)^2=1/4$ 与精确值 $1/6$ 有可见差距——这正是 $r,n$ 不够大时低阶项的表现。

### 5.3 代入成本公式

把 $S_{\mathrm{set}}=r$、$U_{\mathrm{up}}=1$、$C_{\mathrm{chk}}=0$、$\delta=\Theta(1/r)$、$\epsilon=\Theta((r/n)^2)$ 代入 4.2 节的公式。由于 $C_{\mathrm{chk}}=0$，括号里只剩 $U_{\mathrm{up}}/\sqrt{\delta}$ 项：

$$
Q(r)=O\!\left(
r+\frac{1}{\sqrt{\epsilon}}\cdot\frac{1}{\sqrt{\delta}}
\right)
=O\!\left(r+\frac{1}{\sqrt{\delta\,\epsilon}}\right).
$$

先算根号里的乘积：

$$
\delta\,\epsilon=\Theta\!\left(\frac{1}{r}\right)\cdot\Theta\!\left(\frac{r^2}{n^2}\right)=\Theta\!\left(\frac{r}{n^2}\right),
$$

于是

$$
\frac{1}{\sqrt{\delta\epsilon}}=\Theta\!\left(\sqrt{\frac{n^2}{r}}\right)=\Theta\!\left(\frac{n}{\sqrt r}\right),
$$

总成本

$$
Q(r)=O\!\left(r+\frac{n}{\sqrt r}\right).
$$

### 5.4 参数平衡：解出 $r=n^{2/3}$

我们要选 $r$ 使两项之和最小。第一项 $r$ 随 $r$ 递增（缓存越大入场费越贵），第二项 $n/\sqrt r$ 随 $r$ 递减（缓存越大越容易撞中碰撞边）——一个递增一个递减，最优出现在两者**同阶**处。令

$$
r=\frac{n}{\sqrt r}
\;\Longrightarrow\;
r\sqrt r=n
\;\Longrightarrow\;
r^{3/2}=n
\;\Longrightarrow\;
r=n^{2/3}.
$$

代回验证两项确实同阶：

$$
r=n^{2/3};\qquad
\frac{n}{\sqrt r}=\frac{n}{\sqrt{n^{2/3}}}=\frac{n}{n^{1/3}}=n^{2/3}.
$$

（上面用 $\sqrt{n^{2/3}}=n^{1/3}$ 与 $n/n^{1/3}=n^{1-1/3}=n^{2/3}$。）因此

$$
Q=O(n^{2/3}).
$$

**Theorem（Magniez–Santha–Szegedy，Zoo 70）.** 任意 $n$ 顶点已知图上的 graph collision 可用 $O(n^{2/3})$ 次量子查询求解。

### 5.5 常见疑问：check 免费，为什么不是 $\sqrt n$？

学生常在这里产生困惑：既然检查不要钱、图又已知，为什么不能更快？瓶颈不在 check，而在 $\epsilon$ 与 $\delta$ 的乘积。把成本公式改写为

$$
Q=O\!\left(r+\frac{n}{\sqrt r}\right)
$$

就能看清两个障碍各自的来源：分母里的 $\sqrt r$ 来自 $\epsilon=\Theta((r/n)^2)$——一个随机缓存**同时**装下碰撞边两个端点的概率天然是 $(r/n)^2$ 而不是 $r/n$，振幅放大只把这个概率开一次根号，留下的 $n/r$ 因子与 $\delta$ 的 $\sqrt r$ 相乘后只剩 $n/\sqrt r$；而 $r$ 项是缓存本身的入场费。要逼近 $\sqrt n$，必须让 $\epsilon$ 对某个图族变得更大（例如接近完全图时"任意两个标记"都算数，$\epsilon$ 从"指定一对"变成"几乎任意一对"）——这正是第 6–8 节结构参数做的事情，而不是通用算法能白捡的改进。

值得强调与 element distinctness 的对照：两处推导的骨架完全相同（Johnson 图、$\epsilon=\Theta((r/n)^2)$、$\delta=\Theta(1/r)$、同一个平衡），唯一的替换是标记谓词——那里是"缓存中出现两个相等的函数值"，这里是"缓存中出现两个在已知图中相邻的标记顶点"。正因为结构同构，通用指数也相同：**仅知道"关系已知"这一条，并不能改进 $n^{2/3}$**；要改进，必须知道关系本身的更多形状，这正是下面三节的内容。

(nonedge-parameter)=
## 6. 结构参数 I：补图非边数 $\ell$

### 6.1 直觉：接近完全图时，碰撞几乎等价于"有两个标记"

设补图 $\bar G$ 的边数为 $\ell$——即 $G$ 中缺失的边（非边）的总数。完全图 $K_n$ 对应 $\ell=0$；图越稀疏，$\ell$ 越大，最大为 $\binom{n}{2}$。

当 $\ell$ 很小时，$G$ 几乎完全：任取两个不同的顶点，它们不相邻的"例外"至多有 $\ell$ 对。于是问题分解为两步：

1. **是否存在至少两个标记顶点？** 这是纯顶点级问题：先用一次量子计数（quantum counting，即对 Grover 迭代算子做相位估计来数标记个数）区分"标记数为 $0$、$1$、还是 $\ge 2$"；若至少有标记，再用 Grover 搜索实际找到第一个标记顶点 $u$（$O(\sqrt n)$），然后在 $V\setminus\{u\}$ 中搜索第二个标记顶点。在接近完全的图中，第二个标记顶点几乎必然与 $u$ 相邻——不相邻的唯一可能是 $\{u,v\}$ 恰好是 $\ell$ 个非边之一，这正是下一步要排查的例外。若连两个标记都没有，直接回答 no。
2. **已知有两个以上标记后，它们是否某一对相邻？** 由于非边总共只有 $\ell$ 对，"两个标记顶点不相邻"这一事件只能落在那 $\ell$ 个例外对上。对例外对做搜索/计数，代价控制在 $O(\sqrt\ell)$ 量级。

把两步合并，并隐藏数据结构带来的多对数因子，得到

$$
\widetilde O\!\left(\sqrt n+\sqrt\ell\,\right)
$$

型上界（$\widetilde O$ 隐藏 $\mathrm{poly}(\log n)$ 因子）。这里的陈述是启发式的：第二步要把"所有标记对"与"$\ell$ 个例外对"的交集检测做得高效，需要 learning graph 框架的技术细节（Zoo 161、172），本教程只保留成本结构与直觉，不展开其谱分析。

### 6.2 两个极端的检验

- **完全图** $\ell=0$：上界退化为 $\widetilde O(\sqrt n)$。这与直接推理一致——$K_n$ 上 collision 就是"至少两个标记"，而第 3 节的下界 $\Omega(\sqrt n)$ 也适用，故此情形已紧。
- **稀疏图**：$\ell$ 大到 $\Theta(n^2)$，$\sqrt\ell=\Theta(n)$，这个参数化上界失去意义。参数化界的价值从来都是有条件的：它只在"图接近完全"这一结构性承诺下兑现。

(alpha-star-parameter)=
## 7. 结构参数 II：独立集总度 $\alpha^*$

### 7.1 no-instance 的隐藏结构

先观察一个简单但后果深远的事实：

**Lemma（no-instance 的独立性）.** 若标记集 $M=\{v:x_v=1\}$ 中存在两个相邻顶点，则该输入是 yes-instance。等价地，**no-instance 的标记集必为独立集**（independent set，即集合内任意两点不相邻）。

**证明。** 这就是 collision 的定义：存在边 $(u,v)\in E$ 使 $x_u=x_v=1$ 恰好就是"存在相邻的两个标记顶点"。若 $M$ 中有相邻对，collision 存在；反过来 collision 存在意味着 $M$ 含相邻对。取逆否命题即得 no-instance 中 $M$ 独立。Q.E.D.

这个引理的价值在于：算法在"还没找到碰撞"的中间状态下，可以把剩余可能性限制在独立集之内，而图的独立集总度数是个可以预先算好的纯图参数。

### 7.2 参数 $\alpha^*$ 的定义与含义

定义

$$
\alpha^*(G)=\max_{I\ \mathrm{independent}}\ \sum_{v\in I}\deg(v),
$$

即"独立集能携带的最大总度数"。注意它与独立数 $\alpha(G)$（最大独立集的**顶点数**）不同：$\alpha^*$ 按度加权，偏爱包含高度顶点的独立集。由 Lemma，任何 no-instance 中，与标记顶点关联的边端点总数 $\sum_{v\in M}\deg(v)$ 不超过 $\alpha^*(G)$；特别地，与标记顶点关联的候选边至多 $\alpha^*(G)$ 条。这把"剩下还要排查多少东西"从 $m$ 压到了 $\alpha^*$。

### 7.3 Gavinsky–Ito 算法的三步结构

Gavinsky 与 Ito 的算法（Zoo 200，[arXiv:1204.1527](https://arxiv.org/abs/1204.1527)）按度阈值把顶点分成高低两类，结构如下：

1. **搜高度顶点。** 对度超过某阈值的顶点做 Grover 搜索，寻找被标记的高度顶点；每找到一个，就在其邻域内再搜索第二个标记顶点（邻域搜索代价与度的平方根同阶）。若这一步成功，collision 已找到。
2. **若未找到：标记全在低度侧。** 此时由 Lemma，标记集是独立集且全部顶点度有界，其关联的总边端点数受 $\alpha^*(G)$ 控制——"度质量"不可能凭空变大。
3. **按度加权搜索剩余候选。** 对剩余的候选边（其数量已被 $\alpha^*$ 封顶）做加权搜索/抽样，找到碰撞或排除之。

高低度阈值经过平衡后（原文献给出具体平衡计算，此处只陈述结果），总复杂度为

$$
O\!\left(\sqrt n+\sqrt{\alpha^*(G)}\,\right).
$$

逐项读这个表达式：$\sqrt n$ 来自在 $n$ 个顶点中定位标记的 Grover 型搜索；$\sqrt{\alpha^*}$ 来自在至多 $\alpha^*$ 个候选关联中做振幅放大式的排查。当 $\alpha^*$ 接近 $n$ 时，整个界接近 $\sqrt n$ 的下界。

### 7.4 随机稠密图：$\alpha^*$ 的天然主场

取固定密度（如 $p=1/2$）的 Erdős–Rényi 随机图 $G(n,p)$。两个经典的随机图事实（本教程引用而不证明）：

- 最大独立集大小以高概率只有 $O(\log n)$ 个顶点——固定密度下，大集合中"恰好一条边都没有"的概率随集合大小指数衰减，故独立集不可能超过对数规模；
- 每个顶点的度集中在 $\Theta(n)$。

于是任何独立集 $I$ 的总度数满足

$$
\sum_{v\in I}\deg(v)\le |I|\cdot\max_v\deg(v)=O(\log n)\cdot\Theta(n),
$$

即

$$
\alpha^*=O(n\log n)
$$

以高概率成立。代入 7.3 的界：

$$
O\!\left(\sqrt n+\sqrt{n\log n}\right)=O\!\left(\sqrt{n\log n}\right)=\widetilde O(\sqrt n),
$$

其中第二步因为 $\sqrt{n\log n}$ 渐近大于 $\sqrt n$（对数因子使前者更大）。也就是说：**对随机稠密图，graph collision 几乎只需要 $\sqrt n$ 次查询**，与第 3 节的一般下界 $\Omega(\sqrt n)$ 只差对数因子。这回答了第 1 节的猜想的一个重要侧面：一般图最难（$n^{2/3}$），而"典型"的稠密图其实很容易——$n^{2/3}$ 的难度是由特殊构造的最坏图贡献的。

(alpha-treewidth-choice)=
## 8. 结构参数 III：独立数 $\alpha$ 与 treewidth $t$

文献中另有两个参数化上界（Zoo 201）。以 $\alpha=\alpha(G)$ 记独立数（最大独立集的顶点数），已知

$$
O\!\left(\sqrt n\,\alpha^{1/6}\right);
$$

以 $t=\mathrm{tw}(G)$ 记图 $G$ 的树宽（treewidth，衡量图与树的接近程度：树的 $t=1$，$K_n$ 的 $t=n-1$），已知

$$
O\!\left(\sqrt n\,t^{1/6}\right).
$$

两个界的直觉相同：用独立集或树分解把图切成"小边界 bag + 条件独立的大块"。bag 之间（或高交互区域）的顶点先查询缓存，剩下的条件独立部分之间不可能藏着未排查的碰撞边，于是可以分块递归地做 Grover 式搜索。$1/6$ 这个指数来自 bag 大小、缓存规模与递归层数之间的多重平衡，其完整推导超出本教程范围；我们只需要会用这两个界做**条件判断**：

- $\alpha$ 或 $t$ 是常数或缓慢增长时，$\alpha^{1/6}$、$t^{1/6}$ 是小因子，界接近 $\sqrt n$；
- $\alpha$ 或 $t$ 大到 $\Theta(n)$ 时，因子 $\Theta(n^{1/6})$ 把界推回 $n^{2/3}$，参数化不再带来优势。

**这些参数之间没有统一的偏序。** 不同图族由不同参数"接管"：

- **星图**：treewidth 为 $1$（树），$t^{1/6}$ 界给出 $O(\sqrt n)$；但最大独立集是全部 $n-1$ 个叶子，$\alpha^{1/6}=n^{1/6}$，该界只给 $O(\sqrt n\cdot n^{1/6})=O(n^{2/3})$，不紧；
- **接近完全图**：非边数 $\ell$ 小，第 6 节的参数最优；
- **随机稠密图**：$\alpha^*=O(n\log n)$，第 7 节的参数最自然。

因此正确的使用方式是：**图是已知的，先（经典地）算出或估计这些参数，再选择最强的那个界**，而不是声称某一个公式对所有图统一最优。

## 9. 小例子：三个图族上的完整核算

### 9.1 完全图 $K_n$

collision 等价于"至少两个顶点被标记"。算法：Grover 搜索第一个标记顶点；若找到 $u$，在 $V\setminus\{u\}$ 中再 Grover 搜索第二个标记顶点（$K_n$ 中任何其他顶点都与 $u$ 相邻）。两段各 $O(\sqrt n)$，合计 $O(\sqrt n)$，与下界匹配。

用第 7 节的参数复核：$K_n$ 的独立集只能是单个顶点（任取两点都相邻），故

$$
\alpha^*(K_n)=\max_{v}\deg(v)=n-1,
$$

界 $O(\sqrt n+\sqrt{n-1})=O(\sqrt n)$，与直接算法一致。

### 9.2 星图 $K_{1,n-1}$

中心标记时，问题等价于在 $n-1$ 个叶子中搜索标记（第 3 节），$\Theta(\sqrt n)$ 次查询既充分又必要。中心未标记时永远没有碰撞，但算法**事先不知道**中心的标记——必须先花一次查询读中心，再决定是否在叶子上搜索；这不改变渐近复杂度。

用参数复核：星图是树，$t=1$，$O(\sqrt n\,t^{1/6})=O(\sqrt n)$，紧；而 $\alpha=n-1$ 使 $\alpha^{1/6}$ 界退化到 $O(n^{2/3})$——同一图族上两个参数质量迥异，印证第 8 节"按图选界"的原则。

### 9.3 路径 $P_n$

路径是稀疏图，$m=n-1=O(n)$。此时连 2.4 节的朴素"对边做 Grover"都已经给出 $O(\sqrt m)=O(\sqrt n)$：把 $n-1$ 条边当作搜索条目，每条两次查询。同时 $P_n$ 是树，$t=1$，结构化界同样给 $O(\sqrt n)$。通用 $n^{2/3}$ 算法在这里依然正确（它对一切图成立），只是不紧——**通用界是所有图上的保证，结构界是具体图上的改进**，两者不矛盾。

## 10. 应用：triangle finding 与 Boolean 矩阵乘法的子程序

(triangle-finding-reduction)=
### 10.1 从 triangle 到 graph collision 的归约

设 $A$ 是（另一个）图 $H$ 的邻接矩阵，要在 $H$ 中找一个三角形。固定一个候选顶点 $w$，给 $V(H)\setminus\{w\}$ 中的顶点打标记：

$$
x_v=A_{wv}\in\{0,1\},
$$

即"标记 $w$ 的所有邻居"。把 $H$ 删去 $w$ 后的诱导子图记为 $G$（它是**已知**的：$A$ 的相应子矩阵可以翻阅）。现在把归约的两个方向分别验证：

- **充分性。** 若 $G$ 中存在 collision 边 $(u,v)$——即 $x_u=x_v=1$ 且 $(u,v)\in E(G)$——则由标记定义 $A_{wu}=A_{wv}=1$，由 $G$ 的边集定义 $A_{uv}=1$，三个顶点 $w,u,v$ 两两相邻，恰成一个三角形。
- **必要性。** 若 $(w,u,v)$ 是含 $w$ 的三角形，则 $A_{wu}=A_{wv}=1$ 给出 $x_u=x_v=1$，而 $A_{uv}=1$ 给出 $(u,v)\in E(G)$，所以 $(u,v)$ 正是 $G$ 中的一条 collision 边。

两个方向合起来：

$$
\text{“}w\text{ 属于某个三角形”}\iff\text{graph collision on }(G,\{x_v\})\text{ 为 yes}.
$$

对 $w$ 做外层 Grover 搜索（$n$ 个候选），内层调用本教程的 graph collision 算法，就得到一个 triangle finding 算法。

### 10.2 为什么不能简单地"逐个 $w$ 独立运行"

朴素嵌套的浪费在于**重复查询**：对每个 $w$ 都从头建立缓存 $D(S)$，而相邻的 $w$ 之间，标记向量 $\{A_{wv}\}$ 只差一行的内容，大量查询是重复的。Magniez–Santha–Szegedy 的改进（以及后续 learning graph 框架）把外层顶点 $w$、缓存子集 $S$ 与邻接数据放进**同一个嵌套量子行走**里，让内层缓存可以随 $w$ 的更换而增量更新，而非每次推倒重来，由此得到比"外层 $\sqrt n$ 乘内层 $n^{2/3}$"更好的三角形查找指数。同样的思想也出现在 Boolean 矩阵乘法中：判断两个 0-1 矩阵乘积的某项是否非零，就是判断"某行的支持集与某列的支持集是否相交"，把支持集标记录入一个已知图，这正是一个 graph collision 实例。

## 11. 本课小结

**小结。**

- Graph collision：已知图 $G$ + 未知顶点标记 $\{x_v\}$，判断是否有边的两端都被标记。邻接免费，只计标记查询。
- 星图嵌入 Grover 给出一般图族的下界 $\Omega(\sqrt n)$；经典最坏情况需 $\Theta(n)$。
- 朴素"对边 Grover"是 $O(\sqrt m)$：稀疏图上已经最优，稠密图上退化为 $O(n)$，这就是问题的难点所在。
- 通用算法在 Johnson 图 $J(n,r)$ 上做 MNRS 量子行走：setup $=r$、update $=1$、check $=0$、$\delta=\Theta(1/r)$、唯一碰撞边下 $\epsilon=r(r-1)/(n(n-1))=\Theta((r/n)^2)$；平衡 $r=n/\sqrt r$ 得 $r=n^{2/3}$，总成本 $O(n^{2/3})$。
- 结构参数给出特殊图上的改进：补图非边数 $\ell$ 给 $\widetilde O(\sqrt n+\sqrt\ell)$；独立集总度 $\alpha^*$（Gavinsky–Ito）给 $O(\sqrt n+\sqrt{\alpha^*})$，随机稠密图上为 $\widetilde O(\sqrt n)$；独立数与 treewidth 分别给 $O(\sqrt n\,\alpha^{1/6})$ 与 $O(\sqrt n\,t^{1/6})$。参数不可互比，应按已知图结构择界。
- Graph collision 是 triangle finding 与 Boolean 矩阵乘法中的结构化子程序；要做好的 triangle 算法，需要嵌套量子行走来避免跨 $w$ 的重复查询。

## 练习题

**练习 1【问题定义与查询模型】**（→ [2.1 节](#query-model)）

1. 基础：写出 graph collision 的判定条件"存在 $(u,v)\in E$ 使 $x_u=x_v=1$"，并写出比特翻转 oracle $O_x|v,z\rangle=|v,z\oplus x_v\rangle$ 的作用；说明判断"$(u,v)$ 是否为 $G$ 的边"需要几次查询。
2. 进阶：对比无结构搜索、element distinctness 与 graph collision 三者"未知的对象"分别是什么，并解释"图结构已知"为什么把邻接判断变成零查询的经典计算。

> 提示：前两者未知的分别是比特串本身与函数值（连"相等关系"都要查询）；graph collision 的"碰撞关系"写在免费可翻阅的已知图 $G$ 里。

**练习 2【经典基线与朴素量子算法】**（→ [2.2 节](#classical-naive-limits)）

1. 基础：复述对抗者论证：为什么经典确定性算法最坏情况必须查询全部 $n$ 个顶点？
2. 基础：计算"对边 Grover"在路径（$m=n-1$）与完全图（$m=\binom{n}{2}$）上的查询次数，并说明哪种情形没有量子优势。
3. 进阶：设 Grover 找到一个标记顶点 $u$，且 $u$ 的邻域内没有其他标记，解释为什么此时仍不能回答 no。

> 提示：Grover 只保证找到"某一个"标记顶点，而碰撞可能发生在任意一对标记顶点之间。

**练习 3【星图下界】**（→ [第 3 节](#star-lower-bound)）

1. 基础：在星图 $K_{1,n-1}$ 与"中心被标记"承诺下，把"collision 存在"改写为对 $n-1$ 个叶子比特的逻辑 OR，并指出它就是规模 $N=n-1$ 的无结构搜索的判定版。
2. 进阶：证明"一个问题在某个输入子类上的下界自动是整个问题的下界"这一推理，并说明由此得到的 $\Omega(\sqrt n)$ 为什么对"所有图"这一最大图族也成立。

> 提示：一个对所有输入都正确的通用算法，在承诺子类上也必须正确。

**练习 4【Johnson 图量子行走与参数平衡】**（→ [第 4 节](#johnson-walk-parameters)）

1. 基础：逐一说明四个成本量的取值理由——setup $=r$、update $=1$、check $=0$、$\delta=\Theta(1/r)$——并解释"check 零查询"为什么不等于"零电路"。
2. 进阶：设唯一碰撞边为 $(u^*,v^*)$，证明均匀随机 $r$ 元子集同时包含 $u^*,v^*$ 的概率为 $\binom{n-2}{r-2}/\binom{n}{r}$，并化简为 $r(r-1)/(n(n-1))$。进一步说明为什么"唯一碰撞边"是使该概率最小的 yes-instance，从而 $\epsilon$ 可取为该值。
3. 进阶：对 $Q(r)=r+n/\sqrt r$，验证 $r<n^{2/3}$ 时第一项更小但第二项超过 $n^{2/3}$、$r>n^{2/3}$ 时反过来，从而 $r=n^{2/3}$ 确为最优量级（可考察 $Q(r)/n^{2/3}$ 作为 $r$ 的函数的单调分段性）。

> 提示：第 2 题先固定 $u^*,v^*$ 入选、再从剩余 $n-2$ 个顶点中选 $r-2$ 个；标记顶点更多时碰撞边只会更多。

**练习 5【非边数参数】**（→ [第 6 节](#nonedge-parameter)）

1. 基础：写出 $\ell$ 的定义（补图 $\bar G$ 的边数），解释两步分解中"两个标记顶点不相邻"为何只能落在 $\ell$ 个例外对上，并检验 $\ell=0$（完全图）时上界退化为 $\widetilde O(\sqrt n)$、与第 3 节下界匹配。
2. 进阶：构造一族 $\ell=\Theta(n)$ 的图（即补图只有线性条边），说明第 6 节的界 $\widetilde O(\sqrt n+\sqrt\ell)$ 在该族上为 $\widetilde O(\sqrt n)$，严格优于通用的 $O(n^{2/3})$；再给出一族 $\ell=\Theta(n^2)$ 的图说明该界失去优势。

> 提示：从 $K_n$ 中删去 $O(n)$ 条边即得 $\ell=\Theta(n)$ 的图；只有 $O(n)$ 条边的稀疏图自动满足 $\ell=\Theta(n^2)$。

**练习 6【独立集总度参数】**（→ [第 7 节](#alpha-star-parameter)）

1. 基础：写出 $\alpha^*(G)$ 的定义，说明它与独立数 $\alpha(G)$（最大独立集的顶点数）的区别，并复核 9.1 节 $\alpha^*(K_n)=n-1$ 的计算。
2. 进阶：证明：no-instance 的标记集必为独立集。并据此解释：为什么 no-instance 中与标记顶点关联的边数至多为 $\alpha^*(G)$（注意区分"边端点总数"与"边数"），以及这一观察在 Gavinsky–Ito 算法第 3 步中起什么作用。
3. 进阶：计算星图 $K_{1,n-1}$ 与路径 $P_n$ 的 $\alpha^*$，并分别代入 $O(\sqrt n+\sqrt{\alpha^*})$，与第 9 节给出的紧界对比，说明 $\alpha^*$ 界在这两个图族上是否紧。

> 提示：星图的最大总度独立集是全部叶子还是含中心？路径的独立集是隔点取点。

**练习 7【独立数、treewidth 与按图择界】**（→ [第 8 节](#alpha-treewidth-choice)）

1. 基础：对星图分别代入两个参数化界（$\alpha=n-1$、$t=1$），比较 $O(\sqrt n\,\alpha^{1/6})$ 与 $O(\sqrt n\,t^{1/6})$ 在该图族上的强弱。
2. 进阶：为完全图、星图、路径三个图族各选出 $\ell$、$\alpha^*$、$\alpha$、$t$ 中最有利的参数并给出所得量级，进而解释为什么这些参数之间没有统一的偏序、必须"按图择界"。

> 提示：星图与路径都是树（$t=1$）；完全图的 $\ell=0$ 且 $\alpha=1$。

**练习 8【triangle finding 归约】**（→ [10.1 节](#triangle-finding-reduction)）

1. 基础：取 $H$ 为三角形 $w$-$u$-$v$，写出固定 $w$ 时内层实例的顶点集、边集与标记 $x_v$，并验证内层实例为 yes 当且仅当 $x_u=x_v=1$（即 $w,u,v$ 恰成三角形）。
2. 基础：按 10.2 节的论述复述：判断 Boolean 矩阵乘积某项是否非零等价于判断某行的支持集与某列的支持集是否相交，而这正是一个 graph collision 型的问题。
3. 进阶：写出固定顶点 $w$ 时 triangle-to-graph-collision 归约的完整形式化表述：内层图 $G$ 的顶点集、边集、标记各是什么；并解释为什么对所有 $w$ 独立地重新建立缓存会引入重复查询、嵌套量子行走如何避免。

> 提示：相邻候选 $w$ 的标记向量只差邻接矩阵的一行，缓存应随之增量更新而非推倒重来。

## 参考文献与 Zoo 覆盖

- Zoo 编号 70：Magniez--Santha--Szegedy 的一般 $O(n^{2/3})$ 方法（本教程第 4–5 节的 Johnson 图量子行走），以及 graph collision 作为 triangle finding 子程序的提出。
- Zoo 编号 161、172：非边数与独立集参数的 learning/graph-collision 上界（本教程第 6、8 节）。
- Zoo 编号 200：Gavinsky 与 Ito, [A Quantum Query Algorithm for the Graph Collision Problem](https://arxiv.org/abs/1204.1527)（本教程第 7 节的 $\alpha^*$ 算法）。
- Zoo 编号 201：Ambainis 等关于 treewidth 等参数化上界（本教程第 8 节）。