技术摘要：标签对称性下碰撞发现与元素唯一性的紧凑时空下界

问题陈述

本文研究了量子查询复杂度中的一个基本开放问题：确定在寻找均匀随机函数 $f: [M] \to [N]$ 的碰撞时，查询次数（$T$）与内存量（$S$）之间的最优权衡关系。

虽然 BHT 算法 [BHT97] 在具有量子访问（QRACM）的情况下，使用 $O(N^{1/3})$ 的查询次数和 $O(N^{1/3})$ 的经典内存可以实现 $O(N^{1/3})$ 的复杂度，且对数空间的 Grover 搜索需要 $O(\sqrt{N})$ 次查询，但对于中间空间范围内的 $T$ 与 $S$ 的精确关系仍未解决。具体而言，目前尚不清楚是否存在一种算法，如果允许使用更多的空间，可以在显著少于 $O(N^{1/3})$ 次查询的情况下找到碰撞；或者反之，是否可以在不承受 Grover 搜索那样的二次惩罚的情况下，仅用对数级空间实现成功。

作者将重点放在**标签对称算法（label-symmetric algorithms）**这一类上。如果一个算法的策略将函数的输出标签视为可互换的，则该算法是标签对称的；形式化地说，其行为在任何范围置换 $[N]$ 下保持不变。这种限制的动机在于，均匀输入分布和碰撞条件本身都具有范围重标记（range relabeling）的不变性，因此对特定标签进行特殊处理并不会带来本质优势。

方法论

证明结合了三个主要的数学技术环节：

1. 压缩算子技术（The Compressed Oracle Technique）：
   作者利用了压缩算子技术（最初由 Zhandry [Zha19] 提出，并由 Hamoudi 和 Magniez [HM23] 适配用于碰撞发现）。在该框架下，算法对随机函数的认知并非表现为一个经典的表格，而是作为“数据库”的叠加态。最初，数据库仅包含空单元格（$\perp$）。随着算法进行查询，叠加态会演变为包含条目 $(x, f(x))$。算法的进展通过包含至少一个碰撞的数据库上的振幅来追踪。

2. 标签对称性与表示论：
   核心创新在于将标签对称性整合进压缩算子分析中。作者分析了输入寄存器的简化状态 $\rho_I$。对于使用 $S$ 个量子比特的标签对称算法，联合状态的 Schmidt 秩至多为 $2^S$。因此，任何位于 $\rho_I$ 支持集中的向量在对称群 $S_N$（置换范围标签）下的轨道所张成的空间维度至多为 $2^S$。
   作者定义了一个具有 $s$ 个已占用条目的“无碰撞压缩数据库”子空间，记作 $C^\perp_s \cap W^{\otimes s}$，其中 $C^\perp_s$ 代表取值互不相同的状态，而 $W^{\otimes s}$ 代表与压缩算子兼容的状态（正交于“全零”傅里叶态）。

3. 排列图（Arrangement Graphs）的谱分析：
   为了限制 $C^\perp_s \cap W^{\otimes s}$ 空间的维度，作者将该维度与删除映射 $D$ 的核联系起来，该核被证明是排列图 $A_{N,s}$ 的 $(-s)$-特征空间。该图的顶点是单射 $s$-元组，边连接在恰好一个坐标上不同的元组。
   利用对称群的表示论，作者证明了对于 $N \ge 2s$，该特征空间分解为形状为 $(N-s, \mu)$ 的不可约表示（Specht 模）。至关重要的是，他们确立了这些表示的维度随 $N$ 和 $s$ 快速增长，具体而言，只要 $s > 2S / \log_2 N$，维度就会超过 $2^S$。
   此外，作者精细化了这些图之前的谱结果，确定了在最小特征值之上的精确谱间隙（spectral gap）为 $N - 2s + 2$。该间隙控制了投影到无碰撞状态与投影到有效压缩数据库状态之间的差异。

核心贡献与结果

1. 碰撞发现的时空下界

本文证明，任何以常数概率寻找随机函数 $f: [M] \to [N]$ 碰撞的标签对称算法必须满足：
$$T = \Omega(N^{1/3})$$
$$T^2 S = \Omega(N \log N)$$
这些界限是通过证明：在压缩算子模型下，拥有有限空间 $S$ 的算法无法维持一个大规模的无碰撞数据库而得出的。具体而言，如果 $s$ 超过阈值 $2S / \log_2 N$，则包含 $s$ 个条目的数据库上的振幅会被抑制，因为相应的子空间需要比可用量子比特更多的位数来表示必要的对称轨道。

2. 界限的紧致性

作者通过展示现有算法可以匹配这些下界，证明了这些下界是紧致的：

• BHT 算法： 对于 $M=N$，具有表大小 $r$ 的 BHT 算法使用 $T = O(r + \sqrt{N/r})$ 次查询和 $S = O(r \log N)$ 空间。令 $r = N^{1/3}$，得到 $T = O(N^{1/3})$ 且 $T^2 S = O(N \log N)$。
• Ambainis 的量子行走算法： 对于针对 $f: [n] \to [n^2]$ 的元素唯一性搜索版本的量子行走算法，满足 $T = \Omega(n^{2/3})$ 且 $T^2 S = \Omega(n^2 \log n)$。

3. 向元素唯一性的扩展

作为直接推论，本文确立了搜索版本元素唯一性（在非单射函数 $f: [n] \to [n^2]$ 中寻找碰撞）的最优权衡：
$$T = \Omega(n^{2/3})$$
$$T^2 S = \Omega(n^2 \log n)$$
作者指出，尽管元素唯一性的判定版本（判定是否为单射）具有与搜索版本相同的渐近有界误差量子查询复杂度，但本文的下界是明确针对必须输出完整碰撞三元组 $(x_1, x_2, y)$ 的搜索版本进行的。这一结果匹配了 Ambainis 算法的性能，证明了其在标签对称算法类中处理搜索问题的最优性。

4. 技术进展：排列图谱分析

本文提供了对排列图 $A_{N,s}$ 的精细谱分析。它确定了在 $N \ge 2s$ 时的精确最小特征值 ($-s$) 以及精确谱间隙 ($N - 2s + 2$)。这一结果改进了 Chen, Ghorbani, 和 Wong [CGW13] 以及 Araujo 和 Bratten [AB17] 之前的界限，为界定时空权衡证明中的投影误差提供了精确的间隙。

意义与主张

作者声称，他们在标签对称算法类中解决了碰撞发现和元素唯一性搜索版本的最优查询-空间权衡问题。他们认为这种限制是自然的，因为问题实例（均匀分布和碰撞条件）本身就是标签对称的。

论文明确指出，移除标签对称性假设仍然是一个重大的开放问题。虽然可以将任意算法对称化，但标准方法需要存储一个随机置换，这会消耗 $\Theta(N \log N)$ 的空间，从而使下界所追踪的空间参数 $S$ 失效。作者指出，若要将这些结果扩展到所有量子算法，需要一种能够保持空间规模的对称化论证，或是一个无需对称性的证明。

这项工作强调了内存对于量子算法的关键作用，特别是对于像碰撞发现这样高度依赖于存储和访问大型数据库能力的算法。结果表明，如果没有足够的内存（具体而言，空间规模需随 $N^{1/3}$ 缩放），立方根级的量子加速将无法维持，算法将被迫回归到二次方级的 Grover 极限。