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 无结构搜索 难：目标不是”某个被标记的顶点”，而是”一对相邻的被标记顶点”，单次查询无法直接验证；
• 它比 element distinctness 简单：那里的”碰撞关系”（两个函数值相等）是完全未知的，而这里的”碰撞关系”（邻接）就写在已知图 $G$ 里，可以随便翻阅。

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

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

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 }^{\ast }$ 给出的算法（Zoo 200，arXiv:1204.1527），以及 Ambainis 等关于 treewidth 等参数化上界的工作（Zoo 201）。本词条的复杂性论断与这些文献一致，并在正文标明哪些是严格推导、哪些只是启发式解释。

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

2.1 查询模型

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

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

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

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

2.2 经典算法：$\Theta (n)$ 已是最优

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

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

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

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

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

$$O(\sqrt{m})$$

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

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

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

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

3. 下界：星图把 Grover 嵌入进来

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

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

$$\text{collision 存在}⟺\text{某个叶子 }{\ell }_i\text{ 满足 }{x}_{{\ell }_i}=1.$$

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

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

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

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

4. 通用算法 I：Johnson 图量子行走框架

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

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

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

4.2 MNRS 量子行走的成本公式

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

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

MNRS 框架的结论（其推导见 collision 与 element distinctness 教程 对 element distinctness 的完整分析，此处直接引用）是：判定”是否存在标记状态”的总查询成本为

$$Q=O\left(S_{\mathrm{set}}+\frac{1}{\sqrt{ϵ}}\left(\frac{1}{\sqrt{\delta }}{U}_{\mathrm{up}}+C_{\mathrm{chk}}\right)\right).$$

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

• $S_{\mathrm{set}}$ 只付一次：它是整个算法的入场费；
• 外层的 $1/\sqrt{ϵ}$ 来自振幅放大：均匀叠加中只有 $ϵ$ 比例的振幅落在好状态上，把它放大到常数概率需要 $O(1/\sqrt{ϵ})$ 轮——这正是 Grover 迭代里 $\sin \theta \approx \sqrt{ϵ}$ 的几何；
• 每一轮要实现的行走反射算子，本质上要求把行走算子的相位估计做到精度 $\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△S^{\prime }|=2$）。行走的一步就是”扔掉一个顶点、加入一个新顶点”。

对 graph collision，状态取为

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

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

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

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

Setup：$S_{\mathrm{set}}=r$。 制备 $r$ 元子集的均匀叠加是免费的酉操作（制备 $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ 个基矢的叠加不需要 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 教程 中有同一事实的使用）。直觉上：一次随机替换只改变 $r$ 个元素中的一个，要让子集”忘掉”自己的初始状态大约需要 $r$ 步，混合时间的倒数正是 $\Theta (1/r)$ 量级。

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

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

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

5.2 逐步计算 $ϵ$

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

$$ϵ=\frac{\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)}{\left(\genfrac{}{}{0ex}{}{n}{r}\right)}.$$

把组合数展开：

$$\frac{\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)}{\left(\genfrac{}{}{0ex}{}{n}{r}\right)}=\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)}.$$

这里第一步代入了 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\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$，于是

$$ϵ=\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$ 元子集共 $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 个，只有 $\{2,3\}$ 一个被标记，故 $ϵ=1/6$；公式给出 $\frac{2\cdot 1}{4\cdot 3}=\frac{2}{12}=\frac{1}{6}$，一致。此时渐近式 $(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)$、$ϵ=\Theta ((r/n{)}^2)$ 代入 4.2 节的公式。由于 $C_{\mathrm{chk}}=0$，括号里只剩 $U_{\mathrm{up}}/\sqrt{\delta }$ 项：

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

先算根号里的乘积：

$$\delta ϵ=\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 ϵ}}=\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}}⟹r\sqrt{r}=n⟹r^{3/2}=n⟹r=n^{2/3}.$$

代回验证两项确实同阶：

$$r=n^{2/3};\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，而在 $ϵ$ 与 $\delta$ 的乘积。把成本公式改写为

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

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

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

6. 结构参数 I：补图非边数 $\ell$

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

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

当 $\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 })$ 量级。

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

$$\tilde{O}\left(\sqrt{n}+\sqrt{\ell }\right)$$

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

6.2 两个极端的检验

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

7. 结构参数 II：独立集总度 ${\alpha }^{\ast }$

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 }^{\ast }$ 的定义与含义

定义

$${\alpha }^{\ast }(G)=\underset{I\mathrm{independent}}{\max }\sum _{v\in I}\mathrm{deg}(v),$$

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

7.3 Gavinsky–Ito 算法的三步结构

Gavinsky 与 Ito 的算法（Zoo 200，arXiv:1204.1527）按度阈值把顶点分成高低两类，结构如下：

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

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

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

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

7.4 随机稠密图：${\alpha }^{\ast }$ 的天然主场

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

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

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

$$\sum _{v\in I}\mathrm{deg}(v)\le |I|\cdot \underset{v}{\max }\mathrm{deg}(v)=O(\log n)\cdot \Theta (n),$$

即

$${\alpha }^{\ast }=O(n\log n)$$

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

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

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

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 }^{\ast }=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 }^{\ast }(K_n)=\underset{v}{\max }\mathrm{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 矩阵乘法的子程序

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{ 属于某个三角形”}⟺\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)$、唯一碰撞边下 $ϵ=r(r-1)/(n(n-1))=\Theta ((r/n{)}^2)$；平衡 $r=n/\sqrt{r}$ 得 $r=n^{2/3}$，总成本 $O(n^{2/3})$。
• 结构参数给出特殊图上的改进：补图非边数 $\ell$ 给 $\tilde{O}(\sqrt{n}+\sqrt{\ell })$；独立集总度 ${\alpha }^{\ast }$（Gavinsky–Ito）给 $O(\sqrt{n}+\sqrt{{\alpha }^{\ast }})$，随机稠密图上为 $\tilde{O}(\sqrt{n})$；独立数与 treewidth 分别给 $O(\sqrt{n}{\alpha }^{1/6})$ 与 $O(\sqrt{n}{t}^{1/6})$。参数不可互比，应按已知图结构择界。
• Graph collision 是 triangle finding 与 Boolean 矩阵乘法中的结构化子程序；要做好的 triangle 算法，需要嵌套量子行走来避免跨 $w$ 的重复查询。

习题。

1.（推导 $ϵ$）设唯一碰撞边为 $(u^{\ast },v^{\ast })$，证明均匀随机 $r$ 元子集同时包含 $u^{\ast },v^{\ast }$ 的概率为 $\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$，并化简为 $r(r-1)/(n(n-1))$。进一步说明为什么”唯一碰撞边”是使该概率最小的 yes-instance，从而 $ϵ$ 可取为该值。 2.（平衡验证）对 $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$ 的函数的单调分段性）。 3.（计算 ${\alpha }^{\ast }$）计算星图 $K_{1,n-1}$ 与路径 $P_n$ 的 ${\alpha }^{\ast }$（提示：星图的最大总度独立集是全部叶子还是含中心？路径的独立集是隔点取点），并分别代入 $O(\sqrt{n}+\sqrt{{\alpha }^{\ast }})$，与第 9 节给出的紧界对比，说明 ${\alpha }^{\ast }$ 界在这两个图族上是否紧。 4.（独立性引理）证明：no-instance 的标记集必为独立集。并据此解释：为什么 no-instance 中与标记顶点关联的边数至多为 ${\alpha }^{\ast }(G)$（注意区分”边端点总数”与”边数”），以及这一观察在 Gavinsky–Ito 算法第 3 步中起什么作用。 5.（归约）写出固定顶点 $w$ 时 triangle-to-graph-collision 归约的完整形式化表述：内层图 $G$ 的顶点集、边集、标记各是什么；并解释为什么对所有 $w$ 独立地重新建立缓存会引入重复查询、嵌套量子行走如何避免。 6.（参数对比）构造一族 $\ell =\Theta (n)$ 的图（即补图只有线性条边），说明第 6 节的界 $\tilde{O}(\sqrt{n}+\sqrt{\ell })$ 在该族上为 $\tilde{O}(\sqrt{n})$，严格优于通用的 $O(n^{2/3})$；再给出一族 $\ell =\Theta (n^2)$ 的图说明该界失去优势。

参考文献与 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（本词条第 7 节的 ${\alpha }^{\ast }$ 算法）。
• Zoo 编号 201：Ambainis 等关于 treewidth 等参数化上界（本词条第 8 节）。

---

参考资料

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