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

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

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

本课知识点

碰撞与元素唯一性的承诺差异——能写出两个问题的承诺与判定任务，说明承诺问题与完全函数的区别，并用碰撞证据数量的多寡解释 $N^{1/3}$ 与 $N^{2/3}$ 的难度差直觉。
经典基线：生日悖论与线性下界——能推导抽 $r$ 个样本全无碰撞的概率 $P_{\mathrm{no}}\approx e^{-r(r-1)/2N}$，并分别说明 collision 的 $\Theta(\sqrt N)$ 与 element distinctness 的 $\Theta(N)$ 论证。
抽样表加 Grover 算法——能写出建表与表外 Grover 两步，论证二对一承诺下表外恰有 $r$ 个标记项，令两项同阶解出 $r=N^{1/3}$，并定量说明该套路对唯一碰撞退化为 $\Omega(N)$。
量子行走搜索框架与 Johnson 图实现——能写出成本公式 $S+O(1/\sqrt{\delta\epsilon})\cdot(U+C)$、说明三种成本在 Johnson 图 $J(N,r)$ 上分别为 $r$、$O(1)$、$0$ 次查询，并解释两个平方根因子分别来自振幅放大与谱隙。
标记比例、谱隙与参数平衡——能由组合计数导出 $\epsilon=\Theta(r^2/N^2)$、由 Johnson 图特征值导出 $\delta=\Theta(1/r)$，并平衡 setup 与行走步数得到 $O(N^{2/3})$。
查询下界与最优性——能写出两个问题的匹配下界及所用方法，并用"成对证据比单点证据贵"解释下界为何是 $N^{2/3}$ 而非 Grover 式 $\sqrt N$。
查询复杂度与时间复杂度的区分——能解释在叠加的子集上可逆维护 $D(S)$ 为何让朴素数组的 update 时间乘 $r$、总时间达 $O(N^{4/3})$，并说明可逆数据结构与 QRAM 假设如何把额外开销压到 polylog 量级。
k-distinctness、claw 与频率矩推广——能把参数平衡推广到 $k$-distinctness 得 $O(N^{k/(k+1)})$、核验 learning graph 的改进指数，并写出 claw 的乘积图思路与频率矩恒等式 $F_2=N+2\cdot\#\{i<j:f(i)=f(j)\}$。

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^*,j^*\}$，其余 $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\times10^3$ 次查询。注意常数 $c$ 与 $N$ 无关——这正是"$r=\Theta(\sqrt N)$"的含义；到下一节会看到，量子算法把这约 $10^3$ 次压到约 $2\times10^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$：

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

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

\[ p=\frac{r}{N-r}=\Theta\!\left(\frac rN\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}} \;\Longrightarrow\; r^2=\frac{N}{r} \;\Longrightarrow\; r^3=N \;\Longrightarrow\; 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^*,j^*\}$ 的输入上：随机 $r$ 元样本包含 $i^*$ 或 $j^*$ 的概率只有约

\[ \frac{2r}{N} \]

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

\[ Q_{\mathrm{total}} \approx \underbrace{\frac{N}{2r}\cdot r}_{\text{反复建表}} +\underbrace{\sqrt{N}}_{\text{最后一轮 Grover}} =\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$ 的距离。谱隙越大混合越快。
命中概率 $\epsilon$： 在稳态分布下，抽屉里恰好含有完整碰撞对的概率（称为标记比例）。

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

\[ O\!\left(\frac{1}{\delta\epsilon}\right) \]

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

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

\[ S\;+\;O\!\left(\frac{1}{\sqrt{\delta\epsilon}}\right)\cdot(U+C) \]

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

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

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

为什么谱分析里出现的是 $\sqrt{\delta}$ 而不是 $\delta$？ 这是量子行走相对经典行走加速的核心机制，值得多交代一句（不追求严格证明）。Szegedy 的构造把马尔可夫链的转移矩阵 $P$ 提升为两个反射的乘积：一个反射关于"从每个顶点出发的一步转移叠加"，另一个关于对偶方向。与 Grover 迭代一样，两个反射的乘积在关键二维子空间上是旋转，而旋转角由链的谱决定：若 $P$ 的特征值是 $\lambda_j=\cos\varphi_j$，则行走算子相应的特征相位正比于 $\varphi_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{\epsilon}$，与本站 Grover 一课的结果自洽。

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

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

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

\[ |S\triangle S'|=2 \quad\Longleftrightarrow\quad S'= (S\setminus\{i\})\cup\{j\} \ \text{对某}\ i\in S,\ j\notin S. \]

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

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

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

\[ |S\rangle\otimes|D(S)\rangle, \qquad 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{\binom Nr}}\sum_S|S\rangle$ 本身不需要查询（这是计算基矢上的已知叠加）；但对每个 $|S\rangle$ 查询其中全部 $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!$ 份，而标记比例、谱隙都不会因此变好。取子集后，顶点数 $\binom Nr$ 已是描述"容量 $r$ 的抽屉"所需的最小状态空间。另外，均匀叠加 $\frac{1}{\sqrt{\binom Nr}}\sum_S|S\rangle$ 是可高效制备的：先制备 $\{0,1\}^N$ 上 Hamming 权重恰为 $r$ 的 Dicke 型叠加（有已知的高效构造），再把权重串读作子集的特征向量即可；关键是它不依赖 $f$，所以制备本身不花查询。

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

\[ Q(r)=O\!\left(r+\frac{1}{\sqrt{\delta\epsilon}}\right). \]

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

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

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

标记比例 $\epsilon$¶

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

\[ \epsilon= \frac{\#\{S:\{i^*,j^*\}\subseteq S\}}{\#\{S\}} =\frac{\binom{N-2}{r-2}}{\binom Nr}, \]

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

\[ \epsilon =\frac{\dfrac{(N-2)!}{(r-2)!\,(N-r)!}}{\dfrac{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$。全部子集 $\binom{10}{4}=210$ 个；同时包含两个指定元素的子集有 $\binom{8}{2}=28$ 个；于是

\[ \epsilon=\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/\bigl(r(N-r)\bigr)$，其中 $A$ 是邻接矩阵。Johnson 图属于结合方案 (association scheme) 中的经典例子，其特征值有已知的封闭表达式：归一化转移矩阵的特征值为

\[ \lambda_j=\frac{(r-j)(N-r-j)-j}{r(N-r)},\qquad 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(\frac1r\right) \qquad(r\le N/2). \]

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

合成与平衡¶

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

\[ \frac{1}{\sqrt{\delta\epsilon}} =\frac{1}{\sqrt{\frac1r\cdot\frac{r^2}{N^2}}} =\frac{1}{\sqrt{\frac{r}{N^2}}} =\frac{N}{\sqrt r}. \]

注意中间一步：$\delta\epsilon=\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} \;\Longrightarrow\; r^{3/2}=N \;\Longrightarrow\; 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\times10^4$ 次——比经典少了约 50 倍，且两项同阶，印证了平衡。

行走为什么赢过反复抽样？ 值得停下来比较一下这个算法与第 3 节失败方案的差别。反复抽样每一轮都把 $r$ 条已查记录整体丢弃、重新付费；行走则把"换样本"分摊到每一步只换一次元素、只付一次查询。定量地看：唯一碰撞下，要让抽屉里出现完整碰撞对，本质上需要抽到约 $N^2/r$ 量级的"换元素"机会（标记比例 $\epsilon\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$（唯一标记要同时含两个端点，$\epsilon$ 多压了一个 $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}),\qquad 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^*,j^*\}$——单次查询 $f(i)$ 所获得的信息，只有在将来恰好查到配对的 $j^*$ 时才会"兑现"。多项式法把这句话定量化：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\rangle|D(S)\rangle$，一步 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$ 元子集的比例为

\[ \epsilon=\frac{\binom{N-k}{r-k}}{\binom Nr} =\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\epsilon}} =\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}} \;\Longrightarrow\; r^{1+\frac{k-1}{2}}=N^{k/2} \;\Longrightarrow\; r^{(k+1)/2}=N^{k/2} \;\Longrightarrow\; 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\times10^4$，行走步数 $\frac{N^{3/2}}{r}= \frac{10^9}{3.2\times10^4}\approx 3.2\times10^4$，两项再次同阶，总计约 $6\times10^4$ 次查询，而经典算法仍需 $\Theta(N)=10^6$ 次。可以看到 $k$ 从 $2$ 增到 $3$ 时，量子查询数从 $2\times10^4$ 涨到 $6\times10^4$，加速比从约 $50$ 倍缩到约 $17$ 倍——这正是指数从 $2/3$ 爬向 $1$ 的具体表现。

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

的更好查询界。验证两个特例：$k=2$ 时指数为 $\frac34-\frac1{12}=\frac23$，与 Ambainis 一致；$k=3$ 时指数为 $\frac34-\frac1{28}=\frac{21-1}{28}=\frac57\approx0.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, \qquad m_a=\bigl|f^{-1}(a)\bigr|, \]

即 $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{ 对}\}\binom22=1$ 对加 $\{b\text{ 对}\}\binom32=3$ 对共 $4$ 对，$N+2\times4=6+8=14$，一致。对二对一承诺的输入，同样的算法给出 $F_2=N+2\cdot\frac N2=2N$（练习 8 要求补全这一计算）。

多碰撞与可复用行走。 如果任务不是找一对、而是找大量碰撞（例如某些格密码筛法 (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 图量子行走，标记比例 $\epsilon=\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^{\frac34-\frac1{4(2^k-1)}}\right)$。
Claw finding 用两个 Johnson 图的乘积；频率矩 $F_2$ 精确编码碰撞对数；找大量碰撞时用 reusable quantum walk 避免反复 setup。

练习题¶

练习 1【碰撞与元素唯一性的承诺差异】（→ 1 节）

分别写出 collision problem 的两种承诺情形与 element distinctness 的判定任务，并指出哪一个是承诺问题、哪一个是完全函数的判定问题。
证明：二对一承诺的正实例恰有 $N/2$ 个碰撞对；再构造一个 element distinctness 的正实例，使碰撞对只剩一对。据此解释为什么前者的证据"遍地都是"、后者的证据近乎唯一。

提示：二对一情形下每个输出值恰有两个原像，恰好配成一对碰撞。

练习 2【经典基线：生日悖论与线性下界】（→ 2 节）

复算第 2 节的逐步论证：已查 $t$ 个输入且尚未碰撞时，写出第 $t+1$ 个输入不产生碰撞的概率，并把各步相乘得到 $P_{\mathrm{no}}\approx e^{-r(r-1)/2N}$，指出两步近似各用在何处。
取 $N=10^6$：解 $e^{-c^2/2}=1/2$ 求出 $c$，写出以约 $1/2$ 概率发现碰撞所需的查询数；若要求成功概率不低于 $0.9$，$c$ 又应取多大？
用对抗论证说明确定性算法判定 element distinctness 必须 $N$ 次查询；随机算法的 $\Omega(N)$ 下界又依靠什么原则把这一定量结论转移过来？

提示：对手前 $N-1$ 次查询一律回答互不相同的值，这在两种答案下都合法。

练习 3【抽样表加 Grover 算法】（→ 3 节）

写出 Brassard–Høyer–Tapp 算法的两个步骤与表外 Grover 搜索的标记条件；在表内未发现碰撞的二对一输入上，说明表外恰有多少个标记项、标记比例是多少。
最小化 $r+\sqrt{N/r}$：令两项相等解出最优 $r=N^{1/3}$，再用对 $r$ 求导的方法验证最优点的确在两项同阶处。
（抽样失效的定量验证）第 3 节断言：对唯一碰撞用"反复抽表加 Grover"的总成本约为 $\frac{N}{2r}\cdot r+\sqrt N=\Omega(N)$。补全推导：样本含某个指定端点的概率为什么是 $\Theta(r/N)$？若改为"样本同时含两个端点才收工"，成本又如何变化？

提示：同时含两端点的概率约为 $(r/N)^2$，此时表内查重即可发现碰撞，不再需要表外 Grover。

练习 4【量子行走搜索框架与 Johnson 图实现】（→ 4 节）

写出量子行走搜索的总成本公式 $S+O(1/\sqrt{\delta\epsilon})\cdot(U+C)$，说明 $S$、$U$、$C$ 各对应什么操作，以及在 Johnson 图 $J(N,r)$ 上三者的查询次数各是多少。
写出 Johnson 图 $J(N,r)$ 的顶点与相邻定义并计算每个顶点的度；再解释为什么顶点取 $r$ 元子集而不是有序 $r$ 元组。
解释谱隙为何以 $\sqrt\delta$ 而非 $\delta$ 进入成本公式：由 $\lambda_j=\cos\varphi_j$ 与 $\arccos(1-\delta)\approx\sqrt{2\delta}$ 说明行走算子的特征相位与转移矩阵特征值的关系，并指出经典成本 $O(1/(\delta\epsilon))$ 中两个因子各自对应的时间尺度。

提示：行走算子是两个反射的乘积，特征相位是转移矩阵特征值的反余弦。

练习 5【标记比例、谱隙与参数平衡】（→ 6 节）

由 Johnson 图特征值公式 $\lambda_j=\frac{(r-j)(N-r-j)-j}{r(N-r)}$ 计算 $\lambda_1$，推导 $\delta=\frac{N}{r(N-r)}=\Theta(1/r)$，并用"每步只更换抽屉中的一个元素"解释混合时间 $\Theta(r)$ 的直觉。
（精确计数）对唯一碰撞对 $\{i^*,j^*\}$，从 $\binom{N-2}{r-2}/\binom Nr$ 出发，逐步推出 $\epsilon=\frac{r(r-1)}{N(N-1)}$；并对 $N=100$、$r=10$ 分别用两种表达式算出数值、比较与近似 $(r/N)^2$ 的误差。
最小化 $r+N/\sqrt r$：令两项相等解出最优 $r=N^{2/3}$，再用对 $r$ 求导的方法验证最优点确实在两项同阶处；与 $r+\sqrt{N/r}$ 的平衡对照，说明两个指数的差异来自哪一项。

提示：求导得 $1-\frac12 N r^{-3/2}=0$，解出 $r=(N/2)^{2/3}$，与平衡解只差常数因子。

练习 6【查询下界与最优性】（→ 7 节）

写出 element distinctness 与 collision problem 的最优查询复杂度，以及给出匹配下界的两类方法名称；说明上、下界匹配对这两个算法意味着什么。
解释"成对证据比单点证据贵"：为什么单次查询 $f(i)$ 获得的信息只有将来恰好查到配对位置时才"兑现"？这一事实如何把下界从 Grover 式的 $\sqrt N$ 推高到 $N^{2/3}$？

提示：能区分"无碰撞"与"唯一碰撞"的多项式单项式必须同时涉及两个配对位置。

练习 7【查询复杂度与时间复杂度的区分】（→ 8 节）

说明查询模型中哪些操作不计费；解释为什么用普通数组在叠加的 $S$ 上维护 $D(S)$ 会让每步 update 的时间多乘一个 $r$，从而行走阶段总时间为 $O(N\sqrt r)$、在 $r=N^{2/3}$ 时反而慢于经典排序。
可逆哈希、radix tree 与嵌套行走把每次 update/check 的额外时间开销压到什么量级？为什么 update 不能留下会泄露路径信息的垃圾比特？引用本课结论时应分别报告哪两类复杂度？

提示：垃圾比特会把分支信息写入环境，等效于对行走态做了一次非预期的测量。

练习 8【k-distinctness、claw 与频率矩推广】（→ 9 节）

（learning graph 指数）验证 $k=2$ 时 $\frac34-\frac1{4(2^k-1)}=\frac23$；计算 $k=3,4$ 的指数并与普通行走的 $k/(k+1)$ 比较，说明 learning graph 的相对优势随 $k$ 如何变化。
（$k$-distinctness 平衡）对普通 Johnson 图行走推导 $k$-distinctness 的最优 $r=N^{k/(k+1)}$，并验证 $k=2,3$ 时分别回到 $N^{2/3}$、$N^{3/4}$；解释为什么 $k$ 增大时量子加速的余量变小。
（频率矩恒等式）证明 $F_2=N+2\cdot\#\{i<j:f(i)=f(j)\}$，并由此说明：对承诺"$f$ 一一或二对一"的输入，$F_2$ 的两个可能取值各是多少。

提示：$m_a^2$ 恰是"函数值同为 $a$ 的有序对"个数，拆成对角项与非对角项两部分。

参考文献与 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 技术。