# 碰撞与元素唯一性：从抽样加 Grover 到 Johnson 图量子行走

“找两个相同输出”有两种常被混淆的版本。Collision problem 承诺函数要么一一、要么严格二对一；element distinctness 没有这种承诺，只问列表中是否存在任意重复。前者可用 $O(N^{1/3})$ 查询，后者的最优查询复杂度是 $\Theta(N^{2/3})$。本课逐步推导两个指数，并扩展到 $k$-distinctness、claw finding 与多碰撞。

## 1. 两个问题的承诺差异

给定 oracle $f:[N]\to[M]$。

**Collision problem：**承诺 $f$ 为一一函数，或每个像恰有两个原像；判断是哪一种。

**Element distinctness：**无额外承诺；判断是否存在 $i\ne j$ 使

$$
f(i)=f(j),
$$

并可要求输出碰撞对。

二对一承诺意味着正实例有 $N/2$ 个碰撞对，信息丰富；element distinctness 的最坏正实例可能只有一个碰撞对，因此更难。

## 2. 抽样表加 Grover 得到 $N^{1/3}$

对 collision promise：

1. 随机选 $r$ 个输入，查询并把 $(i,f(i))$ 存入排序/哈希表；若表内已碰撞则完成。
2. 对其余输入做 Grover 搜索，标记条件是 $f(j)$ 是否出现在表中。

在二对一情形，样本中每个输出的另一个原像大概率仍在外部，所以外部约有 $r$ 个标记项。Grover 成本

$$
O\!\left(\sqrt{N/r}\right).
$$

总查询数

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

平衡得到

$$
r=N^{1/3},\qquad Q=O(N^{1/3}).
$$

这利用了大量碰撞。若只有唯一碰撞，随机表包含其一个端点的概率仅约 $2r/N$；反复抽表的成本抵消优势，不能直接推出 $N^{1/3}$ 的 element-distinctness 算法。

## 3. Johnson 图状态保存已查询值

Ambainis 算法在 Johnson 图 $J(N,r)$ 上行走。顶点是 $r$ 元子集 $S\subset[N]$，状态连同数据

$$
D(S)=\{(i,f(i)):i\in S\}
$$

一起保存。若 $D(S)$ 内含相同输出，就把 $S$ 标记。

设置均匀叠加及数据需 $S=r$ 次查询。相邻子集只删除一个索引、加入一个索引，所以 update 只需一次新查询（再可逆擦除旧值）。若数据结构按输出值排序或哈希，检查是否有重复不再查询 oracle。

## 4. $N^{2/3}$ 的完整平衡

假设只有唯一碰撞对 $\{i^*,j^*\}$。随机 $r$ 元子集同时包含二者的比例

$$
\epsilon=
\frac{\binom{N-2}{r-2}}{\binom Nr}
=\frac{r(r-1)}{N(N-1)}
=\Theta(r^2/N^2).
$$

Johnson 图随机替换链的谱隙

$$
\delta=\Theta(1/r).
$$

Szegedy 搜索调用 update/check 的次数为

$$
O\!\left(\frac1{\sqrt{\delta\epsilon}}\right)
=O(N/\sqrt r).
$$

所以

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

取

$$
r=N^{2/3}
$$

得到

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

多项式法/adversary 下界也为 $\Omega(N^{2/3})$，故查询最优。严格内容审查仍需同时检查 MathJax 渲染；Sphinx 能解析文档，并不等于每个数学宏都已通过语义校验。

## 5. 数据结构为何是算法的一部分

查询模型把排序、插入和查重视为免费，但真实量子电路必须在叠加的 $S$ 上可逆更新 $D(S)$。若用普通数组并移动 $r$ 个元素，每一步时间会多乘 $r$。可逆哈希、radix tree 或带嵌套更新的量子行走用于把 update/check 压到 polylog 开销。

因此应分别报告：

$$
Q=\Theta(N^{2/3})
$$

是 oracle 查询结论；达到近似相同门时间还需要相干随机访问与碰撞数据结构。新型 multidimensional/electric-network walk 对 $k$-distinctness 已能在若干范围让时间匹配查询到 polylog 因子。

## 6. $k$-distinctness 与 learning graph

$k$-distinctness 要找 $k$ 个输入具有相同输出。直接把 Johnson 顶点标记为“含完整 $k$-碰撞”，唯一目标下

$$
\epsilon=\Theta((r/N)^k),\qquad\delta=\Theta(1/r).
$$

总成本

$$
r+\frac1{\sqrt{\delta\epsilon}}
=r+\frac{N^{k/2}}{r^{(k-1)/2}}
$$

在 $r=N^{k/(k+1)}$ 平衡，给出 $O(N^{k/(k+1)})$。

Learning graph 不要求一次把所有 $k$ 个目标都装进同一普通子集，而是分阶段加载可能属于碰撞结构的变量，并按证书结构重新加权 flow。对常数 $k$，可达到

$$
O\!\left(
N^{\frac34-\frac1{4(2^k-1)}}
\right)
$$

型更好查询界；时间高效实现需要 nested/multidimensional updates。

## 7. Claw、频率矩与多碰撞

Claw finding 给两个函数 $f:X\to R$、$g:Y\to R$，寻找 $f(x)=g(y)$。它可在两个 Johnson 图的乘积上行走，并根据 $|X|,|Y|$ 选择不同子集大小；三函数 claw 和非均匀域需要重新平衡。

频率矩

$$
F_k=\sum_a m_a^k,
\qquad m_a=|f^{-1}(a)|
$$

把“是否有碰撞”推广为估计碰撞数量。若需要寻找大量碰撞，重复从头运行 walk 会浪费已查询数据；reusable quantum walk 在测得一个解后保留/重用其余量子数据，可改善格筛等应用的总成本。

## 8. 小结与习题

- 二对一 collision 有大量标记，抽样表加 Grover 得到 $N^{1/3}$。
- Element distinctness 最坏只有一对，Johnson 图的标记比例与谱隙平衡给出 $N^{2/3}$。
- setup/update/check 和可逆数据结构决定查询优势能否转成时间优势。
- $k$-distinctness 的普通 walk 给 $N^{k/(k+1)}$，learning graph 可进一步改善。

1. 最小化 $r+\sqrt{N/r}$ 与 $r+N/\sqrt r$，比较两个指数。
2. 精确推导唯一碰撞的标记比例。
3. 推导普通 $k$-distinctness walk 的最优 $r$。
4. 说明为什么 Sphinx 成功解析 Markdown 仍不足以证明所有 MathJax 公式语义正确。

## 参考文献与 Zoo 覆盖

- Collision 基线：Zoo 18、21、315，含 [Brassard--Høyer--Tapp](https://arxiv.org/abs/quant-ph/9705002)。
- Element distinctness：Zoo 7、374，核心为 [Ambainis Johnson 图算法](https://arxiv.org/abs/quant-ph/0311001)。
- $k$-distinctness 与时间高效 walk：Zoo 154、172、173、363、464，见 [Multidimensional Quantum Walks](https://arxiv.org/abs/2208.13492)。
- Claw、频率矩与多碰撞：Zoo 277、364、365、535，另含 Zoo 172--173 的 nested update 技术。