作者: Yann Tal

1. 核心物理图象

这项研究致力于解决一个经典计算难题：如何高效地计算大素数 (p) 的阶乘 (n! \mod p)。传统方法需要大约 (\sqrt{p}) 步，被视作一个难以突破的“平方根壁垒”。作者利用量子计算的独特优势，设计了一种新算法，在特定条件下（即 (p-1) 拥有一个大小合适的因子）能够将计算速度提升到 (p^{c/(2c+1)})（其中 (c) 为常数），从而打破了这个壁垒。其核心思想并非直接计算庞大的乘积，而是借助数论中的雅可比和（Jacobi sums），通过量子算法快速找到这些和，再间接地、以更快的速度重构出阶乘的结果。

2. 关键术语解释

• 雅可比和 (Jacobi Sum): 这是数论中的一个重要对象，由多个乘法特征（一种关于模 (p) 的周期函数）的乘积求和得到。在本论文中，它是计算阶乘的关键“密码本”。作者开发了量子算法来高效地重构这些和，这正是实现加速的核心步骤。
• 紧凑表示 (Compact Representation): 雅可比和本身是一个代数整数，常规表示会极其庞大。作者提出以“幂乘积”的形式（如 (\prod \beta_i^{z_i})）来紧凑地存储这些大数，避免直接展开。这就像用指数表示极大数一样，极大地节省了存储空间和计算时间，是算法可行的关键。
• 婴儿步/巨人步算法 (Baby-step Giant-step): 一种经典的算法技巧，用于计算形如 (\prod_{j=1}^M (A+j)) 的区间乘积，其时间复杂度为 (\tilde{O}(\sqrt{M}))。在本算法中，它被用作“辅助工具”，用于处理阶乘中那些未被雅可比和覆盖的剩余部分。

3. 主要贡献

• 突破平方根壁垒：首次在理论上证明，在 (p-1) 拥有合适大小因子的前提下，量子算法能够以低于 (\sqrt{p}) 的复杂度（具体为 (p^{c/(2c+1)} < 1/2) 次方）计算模阶乘，打破了长期存在的经典计算极限。
• 精确重构雅可比和的量子算法：提出了一个全新的量子算法，能够以多项式时间（相对于 (q) 和 (\log p)）精确地、以紧凑表示形式重构出任意阶的雅可比和，而不仅仅是近似值。这使得后续的模运算成为可能，是本工作最核心的技术突破。
• 扩展到模 (p^2) 情形：将上述算法成功推广到计算 (n! \mod p^2) 的情形，这一结果具有独立的数论意义，能够直接用于研究威尔逊素数（Wilson primes）。

4. 研究方法

研究方法是数论与量子算法的深度融合。首先，作者使用了一个关键的数论恒等式（Young 的同余式），将计算 ((aK)! \mod p) 的问题转化为计算雅可比和 (J_a(\chi)) 和 (K!) 的问题。然后，利用一系列量子算法模块来攻克难点：

• 使用 Biasse–Song 算法，在量子环境下解决主理想问题（Principal Ideal Problem），从而找到生成雅可比和所对应理想的代数元素。
• 再利用量子算法计算 S-单位群 (S-unit group)，以校正元素间的单位差异。
• 最后，使用 Van Dam–Seroussi 算法 估计高斯的相位，来精确确定雅可比和相差的单位根倍数。整个过程都贯穿了紧凑表示的思想，确保计算在高维数域中不会因为数据膨胀而失效。

5. 实验结果与结论

论文给出了严格的复杂度分析，证明了在 (q | (p-1)) 的条件下，模 (p) 和模 (p^2) 的阶乘计算都能在 (\tilde{O}(q^c + \sqrt{p/q})) 的期望时间内完成，从而在理论上打破了 (\sqrt{p}) 的壁垒。这一结论表明，量子计算在数论和算法复杂性领域具有超越经典算法的巨大潜力。 论文同时指出了两条重要的开放性问题：1) 如何将算法推广到模 (p^k)（(k>2)）的情形；2) 核心猜想是移除 (q | (p-1)) 这个技术性条件，寻求对所有素数 (p) 都适用的通用量子算法。这些为未来研究指明了方向。

6. 论文标签

量子算法, 量子复杂性, 模拟

📄 点击此处展开/折叠原文 PDF

原文链接： Quantum Algorithms for Modular Factorials