碰撞与元素唯一性

“找两个相同输出”是算法设计中最常见的需求之一：密码学家想知道一个哈希函数是否容易被找到碰撞（生日攻击），数据库系统要检测重复记录，而许多量子算法的核心子程序本质上都是某种碰撞搜索。但在量子查询复杂度的语境下，“碰撞”其实对应两个经常被混淆、难度却截然不同的版本。Collision problem 带有强承诺：函数要么是一一的，要么是严格二对一的；element distinctness 没有任何承诺，只问列表中是否存在任意重复。前者可以用 $O(N^{1/3})$ 次查询解决，后者的最优查询复杂度是 $\Theta (N^{2/3})$。两个指数 $1/3$ 与 $2/3$ 都不是凭空掉下来的：它们分别来自”样本表大小 $r$“与”Grover 搜索成本”、“量子行走维护成本”与”命中标记态成本”之间的平衡。本词条的目标是把这两个平衡逐项推导出来，并沿此框架扩展到 $k$-distinctness、claw finding 与多碰撞问题。

阅读本词条需要的前置知识：Grover 搜索与振幅放大（）、量子行走的基本概念（的量子行走词条有所帮助但不必须）、以及查询模型（oracle model）的约定——我们把一次对 $f(i)$ 的求值记为一次查询，而查询之外的计算暂不计费，到第 8 节再回头清算这笔账。

1. 两个问题的承诺差异

给定一个黑箱函数（oracle）$f:[N]\to [M]$，其中 $[N]=\{1,\dots ,N\}$。我们只能通过查询 $f(i)$ 来获取信息。

Collision problem（碰撞问题）： 承诺 $f$ 满足两种情形之一——要么 $f$ 是一一函数（所有输出互不相同），要么 $f$ 是严格二对一函数（每个像恰有两个原像）。任务是判断属于哪一种情形。

Element distinctness（元素唯一性）： 没有任何承诺。任务是判断是否存在 $i\ne j$ 使

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

在搜索版本中，还要求输出这样一对 $(i,j)$。

承诺的差异为什么重要？看正实例（存在碰撞的情形）中”证据”的数量。二对一承诺意味着：一旦 $f$ 不是一一的，它就有整整 $N/2$ 个碰撞对——每个输出值都参与一对。碰撞证据遍地都是，随机抽样很容易撞上。相反，element distinctness 的最坏正实例可能只有唯一一对碰撞 $\{i^{\ast },j^{\ast }\}$，其余 $N-2$ 个输出全不相同。要从 $N$ 个输入里翻出这唯一的一对，直觉上当然难得多。本词条后面会看到，这个直觉精确地体现在指数上：证据多则 $N^{1/3}$，证据少则 $N^{2/3}$。

还有一点值得强调：collision problem 是一个承诺问题 (promise problem)，算法只需在承诺成立的输入上正确；而 element distinctness 是完全函数（total function）的判定问题。承诺问题可能比对一般输入判定更容易，这本身就是查询复杂度中一个反复出现的主题。

2. 经典算法基线：生日悖论与”必须读完”

在看量子算法之前，先弄清楚经典算法能做到什么，这样才知道量子优势从何而来。

Collision problem 的经典复杂度是 $\Theta (\sqrt{N})$，这就是生日悖论。 具体地，随机均匀地查询 $r$ 个不同的输入 $i_1,\dots ,i_r$。在二对一情形，逐个加入样本：已查 $t$ 个输入且尚未碰撞时，第 $t+1$ 个输入的取值落在前 $t$ 个值上的”另一半”原像共有 $t$ 个（每个已见输出恰有一个未查的原像），剩余未查输入共 $N-t$ 个，所以这一步不产生碰撞的概率是 $1-\frac{t}{N-t}$。于是 $r$ 个样本全无碰撞的概率为

$$P_{\mathrm{no}}=\prod _{t=0}^{r-1}\left(1-\frac{t}{N-t}\right)\approx \prod _{t=0}^{r-1}\left(1-\frac{t}{N}\right)\approx \exp \left(-\sum _{t=0}^{r-1}\frac{t}{N}\right)=\exp \left(-\frac{r(r-1)}{2N}\right),$$

其中第一步近似用了 $N-t\approx N$（我们关心 $r\ll N$ 的情形），第二步用了 $1-x\approx e^{-x}$（$x$ 小时成立），最后一步是等差数列求和。取 $r=c\sqrt{N}$，则 $P_{\mathrm{no}}\approx e^{-c^2/2}$：只要 $c$ 是适当常数，发现碰撞的概率就是常数。这说明 $O(\sqrt{N})$ 次查询足够（一一情形下抽样永远无碰撞，正好给出判定信号）；反过来，少于这个量级时二对一情形下也大概率看不到碰撞，无法区分两种情形，所以 $\Omega (\sqrt{N})$ 也是必要的。这就是”生日攻击”的复杂度来源：$N$ 天中只要约 $\sqrt{N}$ 个人就很可能有生日重合。

数值小例子。 取 $N=10^6$，要求以约 $1/2$ 的概率在二对一情形下发现碰撞：解 $e^{-c^2/2}=1/2$ 得 $c=\sqrt{2\ln 2}\approx 1.18$，即 $r\approx 1.18\times 10^3$ 次查询。注意常数 $c$ 与 $N$ 无关——这正是"$r=\Theta (\sqrt{N})$"的含义；到下一节会看到，量子算法把这约 $10^3$ 次压到约 $2\times 10^2$ 次。

Element distinctness 的经典复杂度是 $\Theta (N)$。 上界平凡：查询全部 $N$ 个输入，排序后扫描相邻项即可，查询 $N$ 次、经典时间 $O(N\log N)$。下界用对抗论证：对手前 $N-1$ 次查询一律返回互不相同的值（这在两种答案下都合法），此时算法仍无法判定第 $N$ 个值是否与之前某个值重复，所以确定性算法必须查满 $N$ 次；随机算法的下界 $\Omega (N)$ 可由 Yao 原则对”全部不同 vs 只有一对重复”的输入分布证得。换言之：最坏情形下经典算法省不掉把整张表读完。

对比一下量子将要达到的目标：collision 从 $\sqrt{N}$ 降到 $N^{1/3}$，element distinctness 从 $N$ 降到 $N^{2/3}$。两者都是多项式级加速，但都不是平方根式的 Grover 加速——这正是本词条要解释的现象。

3. 抽样表加 Grover：collision 的 $O(N^{1/3})$ 算法

第一个量子算法来自 Brassard–Høyer–Tapp（1997，见文末参考文献），思想极其朴素：先抽样建一张小表，再用 Grover 在表外搜索能与表内匹配的元素。 它是”量子算法 = 经典骨架 + Grover 加速部件”的范例。

历史背景值得交代一句：这篇文章发表在 Grover 算法（1996）之后不久，是”Grover 不只能搜一个目标、还能嵌入更复杂算法结构”的最早示范之一；同时它留下的问题——element distinctness 没有二对一承诺、此套路失效——悬置了数年，直到 Ambainis 2003 年的量子行走算法才解决（第 4–6 节）。这段历史说明：$N^{1/3}$ 与 $N^{2/3}$ 之间的差距不是技术欠缺，而是两个问题的本质难度差异（第 7 节的下界将证实这一点）。

算法步骤

对 collision promise（一一或严格二对一），取一个待定的样本大小 $r$：

1. 建表。 随机选取 $r$ 个输入，逐一查询，把 $(i,f(i))$ 存入一张排序表（或哈希表）。如果表内已经出现两个相同的 $f$ 值，直接宣布”二对一”并结束。
2. 表外 Grover 搜索。 在其余 $N-r$ 个未查询的输入上做 Grover 搜索，标记条件为”$f(j)$ 出现在表中”。若搜到，宣布”二对一”；若搜不到，宣布”一一”。

正确性在一一情形是平凡的（表内和表外都不会有匹配）。关键是二对一情形下第 2 步有多少个标记项：由于第 1 步没有在表内发现碰撞，每个已抽样输出的”另一半”原像都不在样本里（否则它就会被查出来造成表内碰撞），因此这 $r$ 个原像全部落在表外的 $N-r$ 个输入中。也就是说外部恰有 $r$ 个标记项，标记比例为

$$p=\frac{r}{N-r}=\Theta \left(\frac{r}{N}\right).$$

由 Grover 搜索的复杂度（在 $N-r$ 个条目中有 $r$ 个目标，查询次数 $O(\sqrt{(N-r)/r})$），第 2 步的成本是

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

参数平衡

总查询数是建表成本与搜索成本之和：

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

这里 $r$ 是我们自由选择的参数：$r$ 越大，表越贵，但表外标记越稠密、Grover 越快；$r$ 越小则相反。两项一升一降，最优出现在两项同阶处（若一项远大于另一项，把参数往降低大项的方向调总能改进）。令

$$r=\sqrt{\frac{N}{r}}⟹r^2=\frac{N}{r}⟹r^3=N⟹r=N^{1/3}.$$

代回得

$$Q=O\left(N^{1/3}+\sqrt{\frac{N}{N^{1/3}}}\right)=O\left(N^{1/3}+N^{1/3}\right)=O(N^{1/3}).$$

数值小例子。 取 $N=10^6$。经典生日攻击需要约 $\sqrt{N}=10^3$ 次查询；量子算法取 $r=N^{1/3}=10^2=100$，建表 $100$ 次查询，Grover 约 $\sqrt{N/r}=\sqrt{10^4}=100$ 次查询，合计约 $200$ 次——恰好是 $2N^{1/3}$，与上面的平衡一致。

为什么这个套路对唯一碰撞失效

这个算法真正利用的是二对一承诺带来的 $r$ 个标记项。假如把同样的思路照搬到只有唯一碰撞对 $\{i^{\ast },j^{\ast }\}$ 的输入上：随机 $r$ 元样本包含 $i^{\ast }$ 或 $j^{\ast }$ 的概率只有约

$$\frac{2r}{N}$$

（$r$ 个样本中每个命中两个特定位置之一的概率）。即使样本幸运地包含了 $i^{\ast }$，表外也只有 $j^{\ast }$ 这一个标记项，Grover 需要 $O(\sqrt{N})$ 次查询才能找到它。算一笔总账：为了让样本命中端点，平均要重复抽表 $N/(2r)$ 轮，每轮建表花 $r$ 次查询，再加上最后一轮成功的 Grover：

$$Q_{\mathrm{total}}\approx \underset{\text{反复建表}}{\underbrace{\frac{N}{2r}\cdot r}}+\underset{\text{最后一轮 Grover}}{\underbrace{\sqrt{N}}}=\frac{N}{2}+\sqrt{N}=\Omega (N).$$

注意第一项与 $r$ 无关——反复抽表的成本正好抵消了小表的好处，总成本退化为线性。结论：抽样加 Grover 不能给出 element distinctness 的 $N^{1/3}$ 算法；要处理唯一碰撞，需要一种”不把已查询数据丢掉重来”的机制。这正是量子行走登场的动机。

4. 量子行走搜索框架：setup、update、check

Ambainis 的 element distinctness 算法（2003，见文末参考文献）属于一大类”量子行走搜索”算法。在深入 Johnson 图之前，先用平实语言把这个框架的直觉讲清楚。

经典类比：边走边攒数据的随机抽查。 想象一个检查员维护一个容量为 $r$ 的抽屉：抽屉里始终放着 $r$ 个已查询过的 $(i,f(i))$ 记录。每一步，他随机扔掉抽屉里的一条记录、随机查一个新输入补进来；每当抽屉里出现两条 $f$ 值相同的记录，就宣布发现碰撞。这个随机过程是状态空间（所有 $r$ 元子集）上的一个马尔可夫链：状态是”抽屉内容”，一步转移是”换一个元素”。它不会从头重来——已查过的数据被保留并复用，这与上一节反复抽表的浪费形成对照。

这个经典随机过程多久能成功？直觉上有两个时间尺度：

• 混合时间 $1/\delta$： 从任意抽屉内容出发，走多少步才能”忘记”起点、接近稳态分布。这里 $\delta$ 是转移矩阵的谱隙 (spectral gap)——第二大特征值与 $1$ 的距离。谱隙越大混合越快。
• 命中概率 $ϵ$： 在稳态分布下，抽屉里恰好含有完整碰撞对的概率（称为标记比例）。

混合一次后，每步有 $ϵ$ 的概率处于标记态，所以经典上大约需要

$$O\left(\frac{1}{\delta ϵ}\right)$$

步（混合 $1/\delta$ 步，再以 $ϵ$ 的概率命中；严格说每 $1/\delta$ 步提供一次”接近独立的抽样机会”）。

量子行走把这个乘积开平方。 Szegedy 提出、并由 Magniez–Nayak–Roland–Santha 等人发展成标准工具的量子行走搜索框架表明：对满足常规条件（遍历、可逆）的马尔可夫链，存在相应的量子行走，能以

$$S+O\left(\frac{1}{\sqrt{\delta ϵ}}\right)\cdot (U+C)$$

的总成本以高概率找到标记顶点。这里三个符号分别是：

• $S$（setup）：制备”稳态叠加”（所有顶点的均匀叠加连同其数据）的成本；
• $U$（update）：实现一步行走（把顶点换成相邻顶点并同步更新数据）的成本；
• $C$（check）：检查当前顶点是否标记（并翻转其相位，供振幅放大使用）的成本。

公式中两个因子各有明确的来源：$1/\sqrt{ϵ}$ 来自振幅放大——把标记振幅从 $\sqrt{ϵ}$ 推到常数需要 $O(1/\sqrt{ϵ})$ 次迭代；$1/\sqrt{\delta }$ 来自量子行走的谱分析——行走算子在”标记子空间”附近的特征相位间隔由 $\sqrt{\delta }$ 控制，相位估计要分辨它就得付出这个精度（这与 Grover 中”旋转角 $\sim \sqrt{p}$“是同一类平方根现象）。对 element distinctness，我们将会看到 $U$ 与 $C$ 都是常数次查询，所以行走搜索的总步数就是 $O(1/\sqrt{\delta ϵ})$，剩下的全部工作就是算出 $\delta$ 与 $ϵ$ 并和 setup 成本 $S$ 做平衡。

为什么谱分析里出现的是 $\sqrt{\delta }$ 而不是 $\delta$？ 这是量子行走相对经典行走加速的核心机制，值得多交代一句（不追求严格证明）。Szegedy 的构造把马尔可夫链的转移矩阵 $P$ 提升为两个反射的乘积：一个反射关于”从每个顶点出发的一步转移叠加”，另一个关于对偶方向。与 Grover 迭代一样，两个反射的乘积在关键二维子空间上是旋转，而旋转角由链的谱决定：若 $P$ 的特征值是 ${\lambda }_j=\cos {\phi }_j$，则行走算子相应的特征相位正比于 ${\phi }_j\approx \sqrt{2(1-{\lambda }_j)}$。谱隙 $\delta =1-{\lambda }_1$ 被开平方，正是因为特征相位是特征值的反余弦——$\arccos (1-\delta )\approx \sqrt{2\delta }$。经典行走要等待 $1/\delta$ 步才能让慢模式衰减，量子行走却只需分辨 $\sqrt{\delta }$ 量级的相位差，一减一除之间就是平方根加速。对完全图上的随机行走（Grover 搜索可看作它的行走版本），$\delta =\Theta (1)$，公式退化为纯振幅放大的 $1/\sqrt{ϵ}$，与 Grover 词条的结果自洽。

5. Johnson 图：用量子行走状态保存已查询值

现在把框架具体化。Ambainis 算法在 Johnson 图 $J(N,r)$ 上行走。

定义。 Johnson 图 $J(N,r)$ 的顶点是 $[N]$ 的所有 $r$ 元子集 $S\subset [N]$；两个顶点 $S,S^{\prime }$ 相邻当且仅当它们恰好相差一个元素，即

$$|S△S^{\prime }|=2⟺S^{\prime }=(S\setminus \{i\})\cup \{j\}\text{对某}i\in S,j\notin S.$$

每个顶点的度是 $r(N-r)$（选扔掉哪个：$r$ 种；选补进哪个：$N-r$ 种）。

一个技术注记（初次阅读可跳过）。 严格的 Szegedy 型行走并不直接在顶点空间 $\{|S⟩\}$ 上作用，而是在”顶点 × 硬币”的张量积空间上作用：硬币寄存器记录”这一步要扔掉哪个元素、补进哪个元素”，行走算子是硬币算子与受控交换的乘积。引入硬币是为了让”从 $S$ 出发的均匀随机转移”成为可逆操作——直接的一步转移会把 $r(N-r)$ 个可能的去向混叠，不可逆。本词条所有复杂度结论不受影响：硬币维度 $r(N-r)$ 只贡献 $\mathrm{polylog}$ 的空间与门开销，update 的查询数仍是一次新查询。

量子态连同数据一起保存。 行走所在的希尔伯特空间不只编码子集 $S$，还携带已经查询过的数据：

$$|S⟩\otimes |D(S)⟩,D(S)=\{(i,f(i)):i\in S\}.$$

若 $D(S)$ 内含有两个相同的输出值（即存在 $i\ne j\in S$ 使 $f(i)=f(j)$），就把 $S$ 标记。换句话说，标记条件”抽屉里有碰撞”正是第 4 节经典类比里的判定方式。

三种成本各是多少？

• Setup： 制备所有 $r$ 元子集的均匀叠加 $\frac{1}{\sqrt{\left(\genfrac{}{}{0ex}{}{N}{r}\right)}}{\sum }_S|S⟩$ 本身不需要查询（这是计算基矢上的已知叠加）；但对每个 $|S⟩$ 查询其中全部 $r$ 个元素以加载 $D(S)$，需要 $r$ 次查询（可并行化为对 oracle 的 $r$ 次受控调用，计 $r$ 次查询）。故 $S=r$。
• Update： 相邻子集之间只删除一个索引、加入一个索引，所以一步行走只需一次新查询（查入新元素 $f(j)$），外加把旧值可逆地擦除（擦除本身不再调用 oracle）。故 $U=O(1)$ 次查询。
• Check： 检查 $D(S)$ 内是否有重复输出。如果数据结构按输出值维护（排序或哈希），查重只是读已存数据，完全不需要再查 oracle。故 $C=0$ 次查询。

为什么顶点取子集而不是序列？ 碰撞条件”$f$ 在 $S$ 上有重复”只与元素集合有关，与排列顺序无关。若把顶点取成有序 $r$ 元组，状态空间会多出 $r!$ 倍的冗余：同一个抽屉内容被复制 $r!$ 份，而标记比例、谱隙都不会因此变好。取子集后，顶点数 $\left(\genfrac{}{}{0ex}{}{N}{r}\right)$ 已是描述”容量 $r$ 的抽屉”所需的最小状态空间。另外，均匀叠加 $\frac{1}{\sqrt{\left(\genfrac{}{}{0ex}{}{N}{r}\right)}}{\sum }_S|S⟩$ 是可高效制备的：先制备 $\{0,1{\}}^N$ 上 Hamming 权重恰为 $r$ 的 Dicke 型叠加（有已知的高效构造），再把权重串读作子集的特征向量即可；关键是它不依赖 $f$，所以制备本身不花查询。

于是行走搜索阶段的总查询数就是行走步数 $O(1/\sqrt{\delta ϵ})$，总查询复杂度形如

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

剩下唯一要做的，是对”唯一碰撞”这一最坏情形算出 $ϵ$，对 Johnson 图算出 $\delta$。

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

本节做两个计算，然后把它们拼起来。

标记比例 $ϵ$

假设整个输入中只有唯一碰撞对 $\{i^{\ast },j^{\ast }\}$（这是 element distinctness 的最坏正实例）。顶点 $S$ 被标记当且仅当 $\{i^{\ast },j^{\ast }\}\subseteq S$。在均匀随机（或均匀叠加）的 $r$ 元子集中，标记顶点所占比例为

$$ϵ=\frac{\#\{S:\{i^{\ast },j^{\ast }\}\subseteq S\}}{\#\{S\}}=\frac{\left(\genfrac{}{}{0ex}{}{N-2}{r-2}\right)}{\left(\genfrac{}{}{0ex}{}{N}{r}\right)},$$

分子是”必须包含 $i^{\ast },j^{\ast }$，其余 $r-2$ 个位置从剩下 $N-2$ 个元素中任选”的计数。把组合数展开逐步化简：

$$ϵ=\frac{\frac{(N-2)!}{(r-2)!(N-r)!}}{\frac{N!}{r!(N-r)!}}=\frac{(N-2)!}{N!}\cdot \frac{r!}{(r-2)!}=\frac{r(r-1)}{N(N-1)}=\Theta \left(\frac{r^2}{N^2}\right).$$

其中第二步约去了公共因子 $(N-r)!$；第三步用了 $\frac{r!}{(r-2)!}=r(r-1)$ 与 $\frac{(N-2)!}{N!}=\frac{1}{N(N-1)}$；最后一步因为 $r,N$ 大时 $r-1\approx r$、$N-1\approx N$。直觉：每个位置以概率 $\approx r/N$ 被抽中，两个特定位置都被抽中约是 $(r/N{)}^2$。

可手算的小例子。 取 $N=10$、$r=4$。全部子集 $\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210$ 个；同时包含两个指定元素的子集有 $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$ 个；于是

$$ϵ=\frac{28}{210}=\frac{2}{15}.$$

用公式验证：$\frac{r(r-1)}{N(N-1)}=\frac{4\cdot 3}{10\cdot 9}=\frac{12}{90}=\frac{2}{15}$，一致。

谱隙 $\delta$

取 Johnson 图上的简单随机行走（每步均匀随机地”扔一个元素、补一个元素”），其转移矩阵是 $P=A/(r(N-r))$，其中 $A$ 是邻接矩阵。Johnson 图属于结合方案 (association scheme) 中的经典例子，其特征值有已知的封闭表达式：归一化转移矩阵的特征值为

$${\lambda }_j=\frac{(r-j)(N-r-j)-j}{r(N-r)},j=0,1,\dots ,r$$

（这里假设 $r\le N/2$）。$j=0$ 给出 ${\lambda }_0=1$（稳态对应的特征值）；谱隙由次大特征值 ${\lambda }_1$ 决定：

$${\lambda }_1=\frac{(r-1)(N-r-1)-1}{r(N-r)}=\frac{rN-r^2-N}{rN-r^2}=1-\frac{N}{r(N-r)},$$

其中第二步展开 $(r-1)(N-r-1)=rN-r^2-N+1$ 再减去 $1$。因此

$$\delta =1-{\lambda }_1=\frac{N}{r(N-r)}=\Theta \left(\frac{1}{r}\right)(r\le N/2).$$

这个 $1/r$ 的直觉值得记住：每一步行走只更换 $r$ 个元素中的一个，要”忘记”初始子集、把抽屉内容整体洗一遍，自然需要 $\Theta (r)$ 步——混合时间就是 $r$，谱隙是它的倒数。这与上面对易拉罐式”一次换一件”过程的直觉吻合。（Ambainis 原算法使用的行走链与此略有差别，但谱隙同为 $\Theta (1/r)$，不影响复杂度结论。）

合成与平衡

把 $\delta =\Theta (1/r)$ 与 $ϵ=\Theta (r^2/N^2)$ 代入行走步数：

$$\frac{1}{\sqrt{\delta ϵ}}=\frac{1}{\sqrt{\frac{1}{r}\cdot \frac{r^2}{N^2}}}=\frac{1}{\sqrt{\frac{r}{N^2}}}=\frac{N}{\sqrt{r}}.$$

注意中间一步：$\delta ϵ=\frac{r}{N^2}$ 中 $r$ 的幂次是 $\frac{r^2}{r}=r$——谱隙里的 $1/r$ 恰好把标记比例 $r^2/N^2$ 里的一个 $r$ 消掉。于是总查询数为

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

同样令两项同阶来平衡（理由同第 3 节：一升一降的两项之和在相等处取最优量级）：

$$r=\frac{N}{\sqrt{r}}⟹r^{3/2}=N⟹r=N^{2/3}.$$

代回：

$$Q=O\left(N^{2/3}+\frac{N}{N^{1/3}}\right)=O\left(N^{2/3}+N^{2/3}\right)=O(N^{2/3}).$$

数值小例子。 仍取 $N=10^6$：经典算法需要约 $10^6$ 次查询，而量子算法取 $r=N^{2/3}=10^4$，setup 花 $10^4$ 次查询，行走阶段 $N/\sqrt{r}=10^6/10^2=10^4$ 步、每步常数次查询，合计约 $2\times 10^4$ 次——比经典少了约 50 倍，且两项同阶，印证了平衡。

行走为什么赢过反复抽样？ 值得停下来比较一下这个算法与第 3 节失败方案的差别。反复抽样每一轮都把 $r$ 条已查记录整体丢弃、重新付费；行走则把”换样本”分摊到每一步只换一次元素、只付一次查询。定量地看：唯一碰撞下，要让抽屉里出现完整碰撞对，本质上需要抽到约 $N^2/r$ 量级的”换元素”机会（标记比例 $ϵ\approx r^2/N^2$ 的倒数，再叠加混合开销），行走把这些机会按每次 $1$ 次查询的单价购入，而反复抽样按每轮 $r$ 次查询、成功率仅 $(r/N{)}^2$ 的批发价购入——折算单价反而更贵。数据复用就是 $N^{2/3}$ 相对线性经典复杂度的全部来源（再加上量子行走的平方根加速）。

与第 3 节对照着看，两个指数的来历就清楚了：collision 的平衡是 $r=\sqrt{N/r}$（标记多，Grover 便宜），解出 $r=N^{1/3}$；element distinctness 的平衡是 $r=N/\sqrt{r}$（唯一标记要同时含两个端点，$ϵ$ 多压了一个 $r/N$），解出 $r=N^{2/3}$。

7. 下界：为什么 $N^{2/3}$ 已经是最优的

上界之外，多项式法 (polynomial method) 与量子对抗法 (quantum adversary method) 都给出了 element distinctness 的 $\Omega (N^{2/3})$ 查询下界（Aaronson–Shi 用多项式法首先证得，Ambainis 的对抗法及 Kutin 的后续工作给出了处理大值域情形的版本）；collision problem 同样有匹配的 $\Omega (N^{1/3})$ 下界。因此

$$Q(\text{element distinctness})=\Theta (N^{2/3}),Q(\text{collision})=\Theta (N^{1/3}),$$

两个算法都是查询复杂度意义下最优的。

下界证明本身超出本词条范围，但直觉可以一句话说清：多项式法把”$T$ 次查询后 acceptance 概率”表示成输入的、次数不超过 $2T$ 的多项式；而”唯一碰撞 vs 无碰撞”这两类输入在局部统计上极其相似，任何能区分它们的多项式必须有足够高的次数，迫使 $T=\Omega (N^{2/3})$。这个”证据太少所以难以区分”的定量形态，与第 1 节的承诺差异直觉首尾呼应。

为什么下界是 $N^{2/3}$ 而不是 Grover 式的 $N^{1/2}$？ 这是初学者最容易问的问题，值得把直觉再推进一步。Grover 下界 $\Omega (\sqrt{N})$ 来自”每次查询只能在一个位置打探目标”；而 element distinctness 的证据是一对位置 $\{i^{\ast },j^{\ast }\}$——单次查询 $f(i)$ 所获得的信息，只有在将来恰好查到配对的 $j^{\ast }$ 时才会”兑现”。多项式法把这句话定量化：acceptance 多项式里能区分两类输入的单项式必须同时涉及两个配对位置，这相当于要求多项式次数翻倍量级地增长，下界于是从 $\sqrt{N}$ 被推高到 $N^{2/3}$。量子对抗法给出同一结论的另一视角：把”无碰撞输入”逐个换成”有一对碰撞的输入”，每次查询最多在目标函数值上积累 $\Theta (\sqrt{r}/N)$ 量级的进展（$r$ 个已定位的候选对摊到 $N$ 个位置上），积累满 $\Omega (1)$ 需要 $N^{2/3}$ 步。两种方法的共同信息是：成对证据比单点证据贵，贵的幅度恰好是 $N^{1/6}$。

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

到目前为止，一切都在查询模型下算账：排序、插入、查重都被视为免费。但要宣称一个”时间优势”，这些账必须补交——这是本节要强调的方法论要点，也是阅读所有量子行走文献时的保留条款。

问题在于：真实量子电路必须在叠加的 $S$ 上可逆地维护 $D(S)$。行走态是 ${\sum }_S|S⟩|D(S)⟩$，一步 update 要对所有分支同时完成”删除旧记录、插入新记录”，且不能留下会泄露路径信息的垃圾比特（否则相干叠加被破坏）。如果用普通数组存放 $D(S)$，插入一个元素可能要在最坏处移动 $r$ 个已有元素，每一步的时间就多乘一个 $r$ 因子——总共 $O(N/\sqrt{r}\cdot r)=O(N\sqrt{r})$，在 $r=N^{2/3}$ 时是 $O(N^{4/3})$，反而比经典排序还慢。

补救办法是精心设计支持可逆操作的数据结构：可逆哈希、radix tree（字典树），以及在行走内部再嵌套一层小行走来分摊更新成本等技术，可以把每次 update/check 的额外时间开销压到 $\mathrm{polylog}(N)$ 量级。因此，引用本词条结论时应分别报告：

• $Q=\Theta (N^{2/3})$ 是 oracle 查询复杂度结论；
• 要达到近似相同的门时间，还需要相干随机访问（QRAM 类的假设）与上述碰撞数据结构配合，实际时间界通常写成 $N^{2/3}\cdot \mathrm{polylog}(N)$ 并依赖具体模型。

这一区分对后续发展同样关键：新型的 multidimensional / electric-network quantum walk（见文末 Zoo 172、173、464 及相关文献）对 $k$-distinctness 已能在若干参数范围内让时间复杂度匹配查询复杂度到 polylog 因子——“若干范围”是模型依赖的保留条件，使用时需要核对原文假设。

9. $k$-distinctness 与 learning graph

问题推广。 $k$-distinctness 要求判定是否存在 $k$ 个互不相同的输入 $i_1,\dots ,i_k$ 具有相同输出（$k=2$ 即 element distinctness）。同样按”唯一 $k$-碰撞”的最坏情形分析。

普通 Johnson 图行走。 顶点仍是 $r$ 元子集，标记改为”$S$ 包含完整的 $k$-碰撞”。唯一目标下，$k$ 个指定元素全部落入随机 $r$ 元子集的比例为

$$ϵ=\frac{\left(\genfrac{}{}{0ex}{}{N-k}{r-k}\right)}{\left(\genfrac{}{}{0ex}{}{N}{r}\right)}=\frac{r(r-1)\cdots (r-k+1)}{N(N-1)\cdots (N-k+1)}=\Theta \left(\frac{r^k}{N^k}\right),$$

推导与第 6 节逐字平行：约去 $(N-r)!$ 后，分子剩 $k$ 个因子、分母剩 $k$ 个因子。谱隙不变，$\delta =\Theta (1/r)$。于是行走步数

$$\frac{1}{\sqrt{\delta ϵ}}=\sqrt{\frac{r\cdot N^k}{r^k}}=\frac{N^{k/2}}{r^{(k-1)/2}},$$

总成本

$$Q(r)=O\left(r+\frac{N^{k/2}}{r^{(k-1)/2}}\right).$$

令两项同阶：

$$r=\frac{N^{k/2}}{r^{(k-1)/2}}⟹r^{1+\frac{k-1}{2}}=N^{k/2}⟹r^{(k+1)/2}=N^{k/2}⟹r=N^{k/(k+1)}.$$

代回得 $Q=O(N^{k/(k+1)})$。验证两个特例：$k=2$ 时指数是 $2/3$，回到第 6 节；$k\to \infty$ 时指数趋于 $1$，即查询数趋于线性——碰撞越大越难”漏看”，但量子加速的余量也越小。

数值小例子。 取 $k=3$、$N=10^6$：最优子集大小 $r=N^{3/4}\approx 3.2\times 10^4$，行走步数 $\frac{N^{3/2}}{r}=\frac{10^9}{3.2\times 10^4}\approx 3.2\times 10^4$，两项再次同阶，总计约 $6\times 10^4$ 次查询，而经典算法仍需 $\Theta (N)=10^6$ 次。可以看到 $k$ 从 $2$ 增到 $3$ 时，量子查询数从 $2\times 10^4$ 涨到 $6\times 10^4$，加速比从约 $50$ 倍缩到约 $17$ 倍——这正是指数从 $2/3$ 爬向 $1$ 的具体表现。

Learning graph 的改进。 注意普通行走的一个浪费：它要求一次把所有 $k$ 个目标元素都装进同一个 $r$ 元子集，并为”不在任何碰撞里的杂项元素”也支付了加载成本。Belovs 提出的 learning graph 框架放弃了这种齐整结构：它分阶段加载”可能属于碰撞结构”的变量（先查一批，再以它们为线索查下一批），并按证书（certificate）的组合结构重新为各阶段的流 (flow) 加权。对常数 $k$，这给出形如

$$O\left(N^{\frac{3}{4}-\frac{1}{4(2^k-1)}}\right)$$

的更好查询界。验证两个特例：$k=2$ 时指数为 $\frac{3}{4}-\frac{1}{12}=\frac{2}{3}$，与 Ambainis 一致；$k=3$ 时指数为 $\frac{3}{4}-\frac{1}{28}=\frac{21-1}{28}=\frac{5}{7}\approx 0.714$，优于普通行走的 $N^{3/4}=N^{0.75}$。需要强调的是，learning graph 本身是一个查询复杂度的构造框架，其时间高效实现需要 nested / multidimensional update 技术的支持（见第 8 节的保留条款）。

10. Claw、频率矩与多碰撞

Claw finding。 给两个函数 $f:X\to R$、$g:Y\to R$，寻找一对 $(x,y)$ 使 $f(x)=g(y)$（想象两份名单找共同成员）。它与 element distinctness 的区别在于碰撞发生在两个不同的表之间：单表情形”两个端点都在同一个子集里”，现在一个端点必须来自 $X$、另一个来自 $Y$，子集缓存结构要相应拆分。

算法思路是直接推广第 5–6 节：在两个 Johnson 图的乘积图上行走，顶点是一对子集 $(S,T)$，分别缓存 $f(S)$ 与 $g(T)$，标记条件是两张缓存表有共同输出。与单表情形不同的是，$|X|$ 与 $|Y|$ 不对称时两个子集应取不同大小：设 $|S|=r_1$、$|T|=r_2$，setup 成本是 $r_1+r_2$，标记比例与谱隙都随 $r_1,r_2$ 各自变化，需要重新做一次第 6 节那样的两项平衡（现在是两个自由参数的联合优化）。三函数 claw、非均匀值域等变体也都需要各自重新平衡。这些变体在密码分析（如对 paw/claw 结构的攻击）中反复出现，是”碰撞搜索 + 参数再平衡”这一方法论的练兵场。

频率矩：把”有没有碰撞”推广为”有多少碰撞”。 定义 $f$ 的第 $k$ 阶频率矩

$$F_k=\sum _{a\in [M]}{m}_a^k,m_a=|f^{-1}(a)|,$$

即 $m_a$ 是输出值 $a$ 的原像个数。它与碰撞计数有精确的联系：把 $m_a^2$ 展开为有序对的计数，

$$F_2=\sum _a{m}_a^2=\sum _a\#\{(i,j):f(i)=f(j)=a\}=\#\{(i,j):f(i)=f(j)\}=N+2\cdot \#\{i<j:f(i)=f(j)\},$$

最后一步把有序对拆成对角项 $i=j$（共 $N$ 个）与非对角项（每对无序碰撞贡献 $2$）。所以 $F_2=N$ 当且仅当无碰撞，估计 $F_2$ 就是定量版的 element distinctness；更高阶矩则度量输出的”不均匀程度”。

可手算的小例子。 设 $N=6$，$f$ 的取值列表为 $(a,a,b,b,b,c)$。则 $m_a=2$、$m_b=3$、$m_c=1$，

$$F_2=2^2+3^2+1^2=14.$$

用恒等式验证：无序碰撞对为 $\{a\text{ 对}\}\left(\genfrac{}{}{0ex}{}{2}{2}\right)=1$ 对加 $\{b\text{ 对}\}\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ 对共 $4$ 对，$N+2\times 4=6+8=14$，一致。对二对一承诺的输入，同样的算法给出 $F_2=N+2\cdot \frac{N}{2}=2N$（习题 5 要求补全这一计算）。

多碰撞与可复用行走。 如果任务不是找一对、而是找大量碰撞（例如某些格密码筛法 (lattice sieving) 的子程序要反复收集碰撞对），朴素做法是每找一个就从头重跑一次行走——这浪费了已经花查询换来的数据。Reusable quantum walk 技术针对这一浪费：在测得一个解之后，把剩余的量子数据保留并复用到下一轮搜索中，而不是重新 setup，从而改善这类应用的总成本。这一方向与第 8 节的时间–查询区分密切相关：复用节省的正是反复 setup 的查询与时间。

多参数平衡的共同模式。 回顾全课，从 $N^{1/3}$、$N^{2/3}$ 到 $N^{k/(k+1)}$，所有指数都来自同一个三步操作：(i) 写出 setup 成本（关于缓存大小 $r$ 递增）与搜索成本（关于 $r$ 递减）两项；(ii) 用标记比例与谱隙把搜索成本写成 $r$ 的显式函数；(iii) 令两项同阶解出 $r$。掌握这个模式后，面对 claw、$k$-distinctness 乃至更复杂的证书结构，剩下的工作只是如实写出每一项——指数会自己算出来。这是查询复杂度分析中最值得带走的方法论。

11. 小结与习题

要点回顾：

• 二对一 collision 有大量标记项（样本的 $r$ 个”另一半”全在表外），抽样表加 Grover 的平衡 $r=\sqrt{N/r}$ 给出 $O(N^{1/3})$；经典基线是生日悖论 $\Theta (\sqrt{N})$。
• Element distinctness 的最坏正实例只有一对碰撞，抽样加 Grover 失效（反复建表成本抵消优势）；改用 Johnson 图量子行走，标记比例 $ϵ=\Theta (r^2/N^2)$ 与谱隙 $\delta =\Theta (1/r)$ 经 Szegedy 型框架合成 $O(N/\sqrt{r})$ 步，与 setup 的 $r$ 平衡后给出 $O(N^{2/3})$；多项式法/对抗法下界 $\Omega (N^{2/3})$ 表明其最优。
• 查询优势不等于时间优势：setup/update/check 的电路成本与可逆数据结构（哈希、radix tree、嵌套行走）决定 $N^{2/3}$ 能否转成门时间结论；引用时应分别报告并核对模型假设。
• 普通行走解 $k$-distinctness 给出 $O(N^{k/(k+1)})$（平衡 $r=N^{k/2}/r^{(k-1)/2}$）；learning graph 分阶段加载证书结构，改进到 $O\left(N^{\frac{3}{4}-\frac{1}{4(2^k-1)}}\right)$。
• Claw finding 用两个 Johnson 图的乘积；频率矩 $F_2$ 精确编码碰撞对数；找大量碰撞时用 reusable quantum walk 避免反复 setup。

习题：

1. （平衡练习）分别最小化 $r+\sqrt{N/r}$ 与 $r+N/\sqrt{r}$：令两项相等解出最优 $r$，比较两个指数；再用对 $r$ 求导的方法验证最优点的确在两项同阶处。
2. （精确计数）对唯一碰撞对 $\{i^{\ast },j^{\ast }\}$，从 $\left(\genfrac{}{}{0ex}{}{N-2}{r-2}\right)/\left(\genfrac{}{}{0ex}{}{N}{r}\right)$ 出发，逐步推出 $ϵ=\frac{r(r-1)}{N(N-1)}$；并对 $N=100$、$r=10$ 分别用两种表达式算出数值、比较与近似 $(r/N{)}^2$ 的误差。
3. （$k$-distinctness 平衡）对普通 Johnson 图行走推导 $k$-distinctness 的最优 $r=N^{k/(k+1)}$，并验证 $k=2,3$ 时分别回到 $N^{2/3}$、$N^{3/4}$；解释为什么 $k$ 增大时量子加速的余量变小。
4. （抽样失效的定量验证）第 3 节断言：对唯一碰撞用”反复抽表加 Grover”的总成本约为 $\frac{N}{2r}\cdot r+\sqrt{N}=\Omega (N)$。补全推导：样本含某个指定端点的概率为什么是 $\Theta (r/N)$？若改为”样本同时含两个端点才收工”，成本又如何变化？
5. （频率矩恒等式）证明 $F_2=N+2\cdot \#\{i<j:f(i)=f(j)\}$，并由此说明：对承诺”$f$ 一一或二对一”的输入，$F_2$ 的两个可能取值各是多少。
6. （learning graph 指数）验证 $k=2$ 时 $\frac{3}{4}-\frac{1}{4(2^k-1)}=\frac{2}{3}$；计算 $k=3,4$ 的指数并与普通行走的 $k/(k+1)$ 比较，说明 learning graph 的相对优势随 $k$ 如何变化。

参考文献与 Zoo 覆盖

• Collision 基线：Zoo 18、21、315，含 Brassard—Høyer—Tapp。
• Element distinctness：Zoo 7、374，核心为 Ambainis Johnson 图算法。
• $k$-distinctness 与时间高效 walk：Zoo 154、172、173、363、464，见 Multidimensional Quantum Walks。
• Claw、频率矩与多碰撞：Zoo 277、364、365、535，另含 Zoo 172—173 的 nested update 技术。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch11-query-complexity/collision-element-distinctness
• 内容遵循 CC BY-NC-SA 4.0 许可协议