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.

  • Zoo 编号 201：Ambainis 等关于 treewidth 等参数化上界。