技术摘要：碰撞问题的量子下界

1. 问题陈述

本文研究了在**精确 $k$-对-1 承诺（exact $k$-to-one promise）**下，碰撞问题的量子查询复杂度。给定对字符串 $x \in \mathbb{Z}_q^n$ 的预言机访问，其中 $n = kN$，输入被承诺为精确的 $k$-对-1：即出现的每个符号都恰好出现 $k$ 次。本文主要讨论两个问题：

1. 承诺的 $k$-对-1 查找（Promised $k$-to-one Finding）： 任务是输出构成单个块（一个完整的 $k$-碰撞）的所有 $k$ 个位置。这不同于随机函数的多元碰撞查找，后者的输出可能具有任意的多重性。
2. $k$-对-1 测试（$k$-to-one Testing）： 一个判别问题，用于区分单射输入（所有值均互不相同）和精确的 $k$-对-1 输入。

作者在两种不同的量子查询模型中分析了这些问题：

• 自适应（Adaptive）： 算法可以利用来自先前预言机调用的信息来决定后续的查询。
• 非自适应（单轮，Non-adaptive/One-round）： 算法在一个并行层中进行所有查询。虽然层内的查询可以具有任意程度的纠缠，但来自该层的信息无法影响第二层查询的准备。

2. 研究方法

证明依赖于一个谐波框架（harmonic framework），用于分析访问均匀随机置换（uniform random permutation）的量子算法，该置换被用于生成困难的输入分布。

2.1. 困难分布构建

作者将碰撞问题归约为置换桶查找（Permutation Bucket Finding）。通过使用一个均匀随机置换 $\pi \in S_n$，将置换的输出槽划分为 $N$ 个大小为 $k$ 的公共桶，从而生成平衡的 $k$-对-1 输入。索引 $i$ 处的输入值由包含 $\pi(i)$ 的桶决定。在输入中寻找一个完整的 $k$-碰撞，等价于在置换中寻找映射到单个桶的所有位置。

2.2. 压缩预言机与编码

核心技术工具是基于 Carolan [Car26] 的工作并针对精确 $k$-对-1 输入进行改进的压缩置换预言机（compressed permutation oracle）。

• 数据库表示： 算法的知识由一个部分单射（输入-输出对）的数据库表示。
• 精确编码 ($V$)： 作者构造了一个等距映射 $V$，将置换寄存器映射到数据库寄存器。这种编码保留了“置换度”（与查询次数相关），并利用谐波子空间（harmonic subspaces）（包括值域谐波和定义域谐波）来消除数据库空间中的冗余方向（例如，携带无新信息的均匀扩展）。
• 误差界限： 文中建立了真实置换查询与更新数据库的“记录”查询之间的紧密界限。具体而言，他们限制了在谐波子空间之外进行局部记录查询所引入的误差，表明对于自适应算法，该误差随 $O(T^2/n)$ 缩放；对于未投影的比较，误差随 $O(\sqrt{T/n})$ 缩放。

2.3. 证明策略

• 自适应下界： 证明过程改编了 Liu 和 Zhandry [LZ19] 的部分碰撞层次结构，并将其应用于置换设置。通过追踪“部分碰撞”（拥有 $j$ 个已记录槽位的桶）在连续查询中的增长情况，通过设定部分碰撞数量的阈值并限制单次查询中跨越这些阈值的振幅，证明了构建完整的 $k$-碰撞需要特定次数的查询。证明过程使用了一个投影记录过程（在每次查询后应用定义域投影 $K_D$）来控制模拟误差。
• 非自适应下界： 对于单轮算法，无法进行碰撞的渐进式构建。相反，作者直接分析单次并行查询层后的状态。他们利用单轮查询中固有的算法向量正交性（引理 3.1）来分解状态。随后，他们应用静态占用界限（引理 7.1）来证明在数据库中记录一组预设的 $k$ 个值的概率被限制在 $O((t/n)^k)$，其中 $t$ 是查询次数。即使对于纠缠查询，该界限依然成立。
• 判别下界： 对于 $k$-对-1 测试，作者比较了算法在四种分布下的简化状态：独立标签（Fun/Block$_k$）和不同标签（Inj/Exact$_k$）。他们利用谐波编码来限制具有独立标签的状态与具有不同标签的状态之间的迹距离，表明其变化很小（$O(t/\sqrt{q})$）。

3. 主要贡献与结果

3.1. 自适应承诺的 $k$-对-1 查找

本文为自适应量子算法建立了紧密的下界。

• 结果： 任何以常数概率成功的量子算法都需要 $\Omega_k(n^{\alpha_k})$ 次查询，其中 $\alpha_k = \frac{1}{2} - \frac{1}{2(2k-1)}$。
• 意义： 这与 Liu 和 Zhandry [LZ19] 的自适应算法所达到的上界相匹配。它证实了其算法中的顺序依赖性是本质性的，并且在精确 $k$-对-1 承诺下，即使具有不受限制的自适应性，也不存在进一步的量子加速。

3.2. 非自适应承诺的 $k$-对-1 查找

本文为单轮量子算法建立了紧密的下界。

• 结果： 任何单轮量子算法需要 $\Omega_k(n^{1-1/k})$ 次并行查询。
• 意义： 这与经典生日采样复杂度相匹配。这表明单层查询中的纠缠本身不足以实现自适应算法中所见的量子加速。顺序依赖性是实现加速的基本要求，而非仅仅是特定算法设计的产物。

3.3. 非自适应 $k$-对-1 测试

本文解决了一个关于区分单射输入与 $k$-对-1 输入的非自适应复杂度的开放问题。

• 结果： 任何单轮量子算法需要 $\Omega(\sqrt{n/k})$ 次查询。
• 意义： 这与经典复杂度相匹配，并回答了 Koiran, Landes, Portier 和 Yao [KLPY10] 针对 $k=2$ 情况提出的开放问题。证明过程处理了必须强制执行不同标签的约束，适用于字母表大小 $q \ge n$ 的情况。

4. 意义与主张

本文声称对这些在精确 $k$-对-1 承诺下的碰撞问题的量子查询复杂度提供了完整的刻画。

• 模型分离： 研究结果清晰地分离了自适应性的力量与量子相干性的力量。虽然量子相干性允许在自适应设置中实现加速（超越经典的 $n^{1-1/k}$ 壁垒），但在非自适应（单轮）设置中，它并不能提供渐近优势。
• 最优性： 通过与现有的上界（Liu-Zhandry 对应自适应，经典采样对应非自适应）相匹配，证明了这些下界是紧密的。
• 方法论进步： 作者引入了一种精炼的用于压缩置换预言机的谐波框架。该框架处理了精确 $k$-对-1 输入中固有的依赖关系（即每个值必须恰好出现 $k$ 次），在这种设置下，以往针对随机函数（假设相互独立）的压缩预言机技术无法直接应用。
• 与同期工作的比较： 文中指出，Carolan 和 Majenz [CM26] 以及 Kim [Kim26] 的同期工作改进了压缩置换预言机的模拟。然而，作者认为他们对这些工具的具体应用——特别是用于自适应下界的投影前向查询过程以及用于单轮下界的静态占用界限——产生了实现精确 $k$-对-1 承诺所需的紧密下界。

文章最后指出了一些开放问题，特别是对于 $r \ge 2$ 层级的全轮次层次结构（full round hierarchy）以及 Search $k$-Distinctness 的字母表大小要求，但并未在本文中提出解决方案。