Improved Quantum Algorithms for Black-Box Abelian Group Decomposition

技术摘要：改进的黑盒阿贝尔群分解量子算法

问题陈述
本文探讨了将有限阿贝尔黑盒群 $G$ 分解为其不变因子（即循环群的直积）并识别相应循环生成元的根本问题。在黑盒模型中，群元素由唯一的字符串表示，通过量子或acles访问群运算。虽然 Cheung 和 Mosca (2001) 已经建立了一个用于此任务的多项式时间量子算法，但该算法依赖于分别分解 Sylow $p$-子群，并利用从单个生成元导出的关系进行 Smith 标准型计算。作者研究了能否将 Regev (2025) 的分解算法应用于群分解，以实现改进的资源界限，因为在某些数论猜想下，该算法使用的量子电路和空间比 Shor 算法更小。

方法论
所提出的算法将 Regev 的量子采样和经典格归约框架应用于群分解的背景。其核心方法论包含三个主要技术创新：

1. 分批子群扩展 (Batched Subgroup Extension)： 该算法并非同时处理所有 $O(n)$ 个生成元（这会需要维度为 $O(n)$ 的格和高空间复杂度），而是通过一系列扩展来处理群。它维护一个已知的子群 $H_k$ 的分解，并通过添加一批数量为 $b = O(\sqrt{n})$ 的新采样元素来对其进行扩展。
2. 通过循环划分控制维度 (Dimension Control via Cyclic Partitioning)： 为了将量子格维度保持在 $O(\sqrt{n})$，算法将 $H_k$ 已知的循环因子划分为“小阶”因子（$H_-$，阶 $\le 2^{\sqrt{n}}$）和“大阶”因子（$H_+$，阶 $> 2^{\sqrt{n}}$）。大阶因子的数量被限制在 $s \le \sqrt{n}$。算法构造作为大阶生成元与新批次元素之整数组合的辅助随机元素。这使得关系格可以在维度为 $m = O(\sqrt{n})$ 的空间上定义，而该维度与群的总秩无关。
3. 联合傅里叶采样与格恢复 (Joint Fourier Sampling and Lattice Recovery)： 量子电路在 $H_-$ 的循环坐标和辅助元素的整数坐标上执行联合傅里叶采样。这产生了来自核（kernel）之零化子（annihilator）对偶的样本。经典后处理使用 LLL 算法来恢复关系格的一个短基。该方法论的一个关键组成部分是证明这些关系格以高概率拥有欧几里得范数至多为 $\tilde{O}(\sqrt{n})$ 的向量的整基。这种短基性质是通过借鉴自 Pilatte (2026) 的格点计数论证建立的，该论证利用了特征正交性和随机子集的傅里叶系数估计。

核心贡献

• 算法设计： 作者提出了一种量子算法，用于计算阶数为 $|G| \le 2^n$ 的有限阿贝尔黑盒群的不变因子分解及其循环生成元。
• 资源改进： 与 Cheung-Mosca 算法及其扩展的公模实现相比，该算法实现了量子资源的显著降低：
  • 量子空间： 从 $O(n^2)$ 量子比特减少到 $O(n)$ 量子比特。
  • 电路规模： 不同电路的门计数总和从 $\tilde{O}(n^2 T_{op})$ 减少到 $\tilde{O}(n^{3/2} T_{op})$，其中 $T_{op}$ 是可逆群运算的代价。
  • 总量子时间： 总时间复杂度从 $\tilde{O}(n^3 T_{op})$ 降低到 $\tilde{O}(n^{5/2} T_{op})$。
• 理论证明： 本文提供了严格的证明，证明算法中使用的整数关系格以高概率具有短整基，这是在不增加维度的情况下实现格恢复步骤的必要条件。该证明改编了来自解析数论和有限群上调和分析的技术。

结果
对于一个满足 $|G| \le 2^n$、具有唯一编码且可逆群运算代价为 $T_{op} = \Omega(\sqrt{n})$ 的有限阿贝尔黑盒群 $G$，该算法：

• 以至少 $1 - O(n^{-3/2})$ 的概率计算不变因子分解及相应的循环生成元。
• 使用 $O(\sqrt{n})$ 个不同的量子电路。
• 执行初始化电路 $O(\sqrt{n})$ 次，每次执行扩展电路 $O(n)$ 次，总计执行 $O(n^{3/2})$ 次。
• 需要 $O(n)$ 量子比特的量子空间。
• 执行多项式次数的经典位运算和群运算查询。

意义
本文声称，这项工作成功地将 Regev 分解算法在整数分解中的电路规模优势推广到了更广泛的黑盒阿贝尔群分解问题中。通过在处理 $O(n)$ 个生成元时保持 $O(\sqrt{n})$ 的电路维度，该算法打破了以往方法中固有的二次方空间障碍。结果表明，只要底层的关系格满足特定的短基性质，Regev 分解算法中所见的资源改进（特别是每执行一次时门复杂度从 $O(n^2)$ 降至 $O(n^{3/2})$）可以扩展到群论问题。作者指出，这些改进依赖于修改后的 Regev 型算法（如 Pilatte 所确立）的无条件正确性以及本文所证明的特定格几何特性。