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

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

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

并可通过 oracle 查询。Graph collision 要判断是否存在边 $(u,v)\in E$ 使 $x_u=x_v=1$。它位于 Grover 与 element distinctness 之间：图结构免费已知，数据只有顶点标记；一般图上 $O(n^{2/3})$，特殊图可由独立集、非边数或 treewidth 改善到接近 $\sqrt n$。

## 1. 模型与基本下界

Oracle 为

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

图的邻接关系不计查询，可在经典控制电路中使用。若取星图并承诺中心标记为 1，collision 存在当且仅当某叶子被标记；这就是 $n-1$ 项 Grover 搜索。因此

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

对一般图族成立，经典最坏需 $\Theta(n)$ 标记查询。

直接 Grover 搜索所有 $m$ 条边需 $O(\sqrt m)$ 轮，每轮查询两个端点；dense 图给 $O(n)$，还不是一般最好上界。

## 2. Johnson 图通用 $n^{2/3}$ 算法

选择 $r$ 元顶点子集 $S$，查询并缓存所有 $x_v,v\in S$。若已知图的诱导子图 $G[S]$ 含两端都标记的边，就标记该 walk state。

假设只有一个 collision edge $(u^*,v^*)$，随机 $S$ 包含两端的比例

$$
\epsilon=\Theta((r/n)^2).
$$

Johnson 图谱隙 $\delta=\Theta(1/r)$，setup 为 $r$，update 一次标记查询，check 只查缓存与已知邻接表。故

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

取 $r=n^{2/3}$ 得

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

该证明与 element distinctness 相似，但这里“两个值相等”被替换为“两个标记点在已知图中相邻”。

## 3. 非边少时的补图参数

若 $G$ 接近完全图，两个标记点几乎必相邻。令补图非边数为 $\ell$。算法先用量子计数/搜索判断是否至少有两个标记点；若有，再检查这些标记对是否可能全部落在补图边上。只需重点处理 $\ell$ 个例外关系，得到

$$
\widetilde O(\!\sqrt n+\sqrt\ell)
$$

型上界。完全图 $\ell=0$ 时降为 $\widetilde O(\sqrt n)$；稀疏图补图很大，该参数无优势。

## 4. 独立集总度参数 $\alpha^*$

定义

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

在 no-instance 中，所有标记顶点必构成独立集，因此它们关联的总边端点数至多 $\alpha^*$。Gavinsky--Ito 算法利用这一结构：

1. Grover 搜索高程度标记顶点，并检查其邻域是否含另一标记；
2. 若未找到，剩余标记顶点的度质量受 $\alpha^*$ 控制；
3. 对剩余候选边做按度加权搜索/抽样。

高低度阈值平衡后得到

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

Erdős--Rényi 固定密度随机图的最大独立集通常只有 $O(\log n)$ 个顶点，而每点度 $\Theta(n)$，故

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

以高概率成立，复杂度 $O(\sqrt{n\log n})$，接近 lower bound。

## 5. 其他结构参数

已知上界还包括

$$
O(\sqrt n\,\alpha^{1/6})
$$

（$\alpha$ 为最大独立集大小）及

$$
O(\sqrt n\,t^{1/6})
$$

（$t$ 为 treewidth）。直觉是用独立集/树分解把图划成小边界 bag，先对 bag 或高交互区域查询，再对条件独立部分递归 Grover。

这些参数不总能比较：star 的 treewidth 小但最大独立集大；接近完全图非边少；随机 dense 图由 $\alpha^*$ 最自然。算法应按已知图结构选择界，而不是声称某一公式统一最优。

## 6. 为什么它是 triangle finding 子程序

固定一个候选顶点 $w$，将其他顶点标记为

$$
x_v=A_{wv}.
$$

若已知图 $G$ 的某条边 $(u,v)$ 两端都被标记，则 $(w,u,v)$ 构成三角形。因此对 $w$ 的外层搜索与 graph-collision 内层算法组合可找 triangle。

直接对每个 $w$ 独立运行会重复边查询；nested quantum walk/learning graph 把 $w$、缓存顶点集和邻接数据联合起来，才得到优于简单嵌套的 triangle 指数。Boolean 矩阵乘法中，行/列支持相交也可编码成 graph collision。

## 7. 小例子

完全图 $K_n$：collision 等价于“至少两个标记”，$O(\sqrt n)$ 查询足够。

Star：中心标记时等价 Grover 搜索叶子，给 lower bound；中心未标记则永远 no，但算法不知道中心标记前需查询。

路径 $P_n$：treewidth 1，结构化动态/分治搜索可接近平方根；通用 $n^{2/3}$ 仍正确但不紧。

## 8. 小结与习题

- 通用 Johnson walk 缓存 $r$ 个顶点标记，平衡得到 $n^{2/3}$。
- Star 嵌入 Grover，给一般 $\Omega(\sqrt n)$ 下界。
- 补图非边数、独立集总度和 treewidth 给特殊图更强界。
- Graph collision 是 triangle finding 和 Boolean matrix multiplication 的结构化子程序。

1. 推导固定 collision edge 被随机 $r$ 集包含的概率。
2. 计算 $K_n$、star、path 的 $\alpha^*$。
3. 解释 no-instance 标记集为何必独立。
4. 写出固定 $w$ 的 triangle-to-graph-collision 归约。

## 参考文献与 Zoo 覆盖

- Zoo 编号 70：Magniez--Santha--Szegedy 的一般 $O(n^{2/3})$ 方法。
- Zoo 编号 161、172：非边数与独立集参数的 learning/graph-collision 上界。
- Zoo 编号 200：Gavinsky 与 Ito, [A Quantum Query Algorithm for the Graph Collision Problem](https://arxiv.org/abs/1204.1527).
- Zoo 编号 201：Ambainis 等关于 treewidth 等参数化上界。