碰撞与元素唯一性：从抽样加 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 覆盖