⚛️ quantum physics

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth

本文介绍了一种紧凑型量子电路，该电路通过一种用于计算雅可比符号的新型空间高效算法，在亚线性空间和深度内，以多项式时间对一类特定的经典难题整数进行分解。

原作者： Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk

发布于 2026-07-07

📖 1 分钟阅读🧠 深度阅读

原作者： Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你有一个巨大的、锁着的保险箱（一个大数字），你想找到它的组合（它的质因数）来打开它。几十年来，破解这种保险箱的最佳方法是 Shor 算法，这是一种著名的量子方法。但 Shor 算法就像试图用一个巨大的、工业级的机械臂去破解那个保险箱。它需要巨大的空间，挥动起来需要很长时间，并且消耗大量能量。它很强大，但目前我们还没有能够制造出那么大机器的硬件。

这篇论文介绍了一种新工具，叫做 Jacobi 分解电路 (Jacobi Factoring Circuit)。请不要把它看作是一个巨大的机械臂，而是一个轻巧的、口袋大小的锁匠工具。它是专门为打开一种特定“类型”的保险箱而设计的，这种保险箱在密码学中非常常见，但具有一种特殊的“弱点”。

以下是该论文通过简单类比进行的拆解：

1. 目标：一种特定类型的保险箱

作者并不是试图破解所有类型的保险箱（比如现在互联网上使用的标准 RSA 锁），而是针对一种特定形状制造的保险箱： $N = P^2 \times Q$ 。

想象一个由两部分组成的保险箱：一个沉重的正方形块 ( $P^2$ ) 和一个较小的、不规则的块 ( $Q$ )。
论文关注的情况是，这个较小的块 ( $Q$ ) 比整个保险箱显著要小，但又没小到经典计算机可以轻易破解的程度。
陷阱： 如果这个较小的块太小，经典计算机已经可以破解它了。如果它太大，这种新方法就没用了。但在“金发姑娘区”（即 $Q$ 恰到好处时），这种新的量子方法就会大放异彩。

2. 旧方法 vs. 新方法

旧的方法 (Li, Peng, Du, and Suter - 2012)：
之前的研究人员发现了一种使用量子力学破解这些特定保险箱的方法。然而，他们的方法就像是用一台巨大的望远镜去观察一只微小的蚂蚁。为了找到组合，他们必须观察整个保险箱（所有的 $N$ 位），这需要海量的量子存储器（量子比特）和时间。

新的方法 (本论文)：
作者意识到他们不需要观察整个保险箱。他们只需要观察那个较小的、不规则的块 ( $Q$ )。

类比： 想象你试图在一座巨大的图书馆里寻找一把特定的钥匙。旧的方法说：“搜索图书馆里的每一本书。”新方法说：“实际上，钥匙只隐藏在存放不规则块的那个小区域里。让我们只搜索那个微小的区域。”
结果： 通过专注于这个较小的部分，他们将所需的空间（量子比特）和深度（时间/步骤）降低到了之前认为的极小比例。他们实现了亚线性空间 (sublinear space)，这意味着所需的内存增长速度远慢于数字本身的规模。

3. 秘密工具：“雅可比符号 (Jacobi Symbol)”

他们是如何做到只观察那部分小区域的呢？他们使用了一个名为 雅可比符号 (Jacobi Symbol) 的数学工具。

隐喻： 把雅可比符号想象成一面特殊的“魔镜”。如果你把一个数字举向它，镜子会反射出一个简单的“是”或“否”（或 +1 或 -1），从而告诉你这个数字与保险箱组合之间的某种关系。
创新点： 这篇论文最大的技术突破在于构建了一个全新的、超高效版本的这种“魔镜”。
- 旧的镜子很笨重，要求你必须把整个保险箱握在手里才能使用。
- 新的镜子很小巧。即使你手里只有一个保险箱的微小碎片，只要你知道剩余的部分是“经典”的（固定的且已知的），它就能工作。
- 这使得量子计算机可以在不需要将其巨大的数字存储在内存中的情况下处理信息。

4. 这究竟能做什么？

该论文声称这个电路可以：

使用近线性门 (near-linear gates)（非常高效的步骤）来分解 (Factor) 这些特定类型的数字 ( $P^2Q$ )。
使用亚线性空间 (sublinear space)（比数字本身更少的内存）。
使用亚线性深度 (sublinear depth)（比之前的方法更快地完成任务）。

重要的局限性： 论文非常明确地指出，这并不会破解标准的 RSA 加密（RSA 使用的是 $N = P \times Q$ ，两个不同的质数）。它只破解具有这种特定“平方”结构的数字。然而，作者指出，这种特定结构已被用于其他密码系统，因此这在相关领域仍是一个重要的发现。

5. “量子特性证明”

论文建议可以使用这个新电路来证明一台计算机是真正的量子计算机。

类比： 想象一位魔术师声称他能从帽子里变出一只兔子。为了证明这一点，他通常需要做一个巨大且复杂的戏法。
这个新方法就像是一位魔术师，可以通过一个简单、快速的手势，从一个极小的帽子里变出一只兔子。它更容易被验证，并且对“舞台空间”（硬件）的要求更低，使其成为在不久的将来演示量子能力的一种更实际的方式。

总结

作者构建了一个专门的、轻量级的量子工具，它比以往任何方法都更高效地破解了一种特定类型的数学锁。他们之所以能做到这一点，是因为他们意识到不需要搬运整个锁，只需要专注于那个较小的、脆弱的部分，并且他们构建了一个新的、微小的“镜子”（算法）来帮助他们观察。虽然它目前还不能破解最著名的锁（RSA），但它证明了对于某些困难问题，量子计算机可以比我们想象的更加微型且高效。

技术摘要：雅可比分解电路 (The Jacobi Factoring Circuit)

问题陈述
当前的量子分解算法（如 Shor 算法以及 Regev 最近的改进方案）在应用于近期设备时，面临着高资源需求的显著障碍。具体而言，分解一个 $n$ 位整数通常需要 $\tilde{O}(n^2)$ 或 $\tilde{O}(n^{3/2})$ 个门以及 $\tilde{O}(n)$ 个量子比特。虽然空间复杂度已降低至 $\tilde{O}(n)$ 甚至 $O(n)$ ，但对于经典难题级别的整数分解，实现亚线性 (sublinear) 的空间和深度仍是一个开放性挑战。此外，现有的量子算法似乎无法从输入整数的特定结构属性（例如较小的无平方因子部分）中获得多项式级的收益，这与某些经典算法不同。

本文探讨了这样一个问题：针对一类其难度预期等同于 RSA 的整数（但不包括 RSA 整数本身），量子电路是否可以实现（近）线性门计数，同时以亚线性空间和深度运行。

方法论
作者提出了“雅可比分解电路”，该电路基于 Li、Peng、Du 和 Suter [LPDS12] 的无平方分解算法。该方法由三个主要技术组件组成：

对 LPDS 的精细化分析（第 3 节）：
原始的 LPDS 电路通过在所有 $x \in [1, N]$ 上创建均匀叠加态并计算雅可比符号 $(\frac{x}{N})$ 来计算整数 $N = A^2 B$ 的无平方分解。作者证明，无需对整个范围 $[1, N]$ 进行叠加。通过结合 Shor 的周期查找分析与高斯和界限（Gauss sum bounds），他们证明了通过在一个更小的范围 $[1, \text{poly}(B_{\max})]$ 上进行叠加（其中 $B_{\max}$ 是无平方部分 $B$ 的上界）就足以以常数概率恢复 $B$ （或一个质因子）。这种缩减使得电路能够以与 $\log B$ 成比例的空间运行，而非 $\log N$ 。
亚线性空间的雅可比符号计算（第 4 节）：
LPDS 方法中的计算瓶颈在于计算当 $x$ 在叠加态中且 $N$ 为大型经典整数时的雅可比符号 $(\frac{x}{N})$ 。标准的算法（扩展欧几里得算法、二进制 GCD 算法）需要与 $\log N$ 成线性关系的存储空间。
作者引入了一种新的量子算法，用于在 $\log x \ll \log N$ 时计算 $(\frac{x}{N})$ 。其核心创新是受蒙哥马利约减（Montgomery reduction）和二进制 GCD 算法启发的一种“反向”长除法变体。
- 机制： 该算法并非寻找一个使 $x$ 的倍数匹配 $N$ 的最高有效位 (MSB) 的值（标准长除法），而是寻找一个 $kx $，使得$ N - kx$ 的最低有效位 (LSB) 与 $N$ 相匹配（即有效地将这些位清零）。
- 空间效率： 通过从 LSB 开始以大小为 $m$ （其中 $m \approx \log x$ ）的块处理 $N$ ，该算法仅需在量子层面存储运行总和的前 $O(m)$ 位。低阶位是经典已知的，可以被撤销计算或回收利用。
- 复杂度： 这产生了一个门计数为 $\tilde{O}(n)$ 、空间为 $\tilde{O}(m)$ 、深度为 $\tilde{O}(n/m + m)$ 的电路。
特殊整数的完全分解（第 5 节）：
论文提供了一个黑盒归约，证明了用于无平方分解的算法可以完全分解其质因数具有不同指数的整数（即所谓的“特殊整数”， $N = p_1^{\alpha_1} \dots p_r^{\alpha_r}$ ，其中所有 $\alpha_i$ 均不相同）。
- 方法： 该算法递归地使用无平方分解来分离出奇数指数质数的乘积。通过计算原数与派生值之间的 GCD，它可以分离出一个单一的质因子。这一过程重复进行，直到获得完整的分解。此方法类似于 Yun 对多项式分解的算法。

核心贡献与结果

定理 1.1（非正式）： 存在一个量子电路，可以分解任何形式为 $N = P^2 Q$ $N = P^{2} Q$ （其中 $P, Q$ $P, Q$ 为质数且 $\log Q = \Theta(n^a)$ $lo g Q = Θ (n^{a})$ ， $a \in (2/3, 1)$ $a \in (2/3, 1)$ ）的 $n$ $n$ 位整数，其使用：
- 门数： $\tilde{O}(n)$
- 量子比特： $\tilde{O}(m)$ （其中 $m = \log Q$ ）
- 深度： $\tilde{O}(m + n/m)$
  当 $m = \Theta(n^a)$ 且 $a \in (0, 1)$ 时，空间和深度相对于 $n$ 均为亚线性。
首次实现亚线性空间的分解： 据作者所知，这是第一个在经典难题分解问题上实现亚线性量子比特数的多项式时间量子电路。
与经典难度的比较： 对于形式为 $N = P^2 Q$ 且 $\log Q \ge \tilde{\Omega}((\log N)^{2/3})$ 的整数，目前尚无已知的经典专用算法（如 Lenstra 椭圆曲线法）能比通用分解算法（数域筛法）提供渐近意义上的加速。因此，这里的量子优势不仅在于利用了经典弱点，更在于实现了在这一区间内经典算法无法实现的资源缩减。
量子性的证明： 该电路支持以亚线性空间复杂度进行基于分解的量子性证明。对于 $\log Q \approx n^{2/3}$ 的 $N = P^2 Q$ ，该电路使用 $\tilde{O}(n)$ 个门、 $\tilde{O}(n^{2/3})$ 的深度和 $\tilde{O}(n^{2/3})$ 个量子比特。这在量子比特数与深度/门数的乘积方面优于 Shor 算法和 Regev 算法。

意义与声明
论文声称，雅可比分解电路通过大幅降低空间和深度需求，代表了在近期或中期量子设备上实现整数分解的重要进展。

独立性： 以亚线性空间计算雅可比符号的技术具有独立的学术价值，并可推广到计算 GCD 和模逆运算。
局限性： 作者明确指出，其方法并不直接分解 RSA 整数（两个大小相近的质数的乘积），因为 RSA 中的无平方部分 $B$ 为 1。该方法适用于无平方部分较小但非平凡的整数。
谦逊态度： 作者指出，虽然渐近缩放得到了改进，但并未深入分析具体的成本（门计数、纠错开销），且实现分解 2048 位整数仍是未来的课题。他们也承认，该算法目前尚未扩展到分解一般的无平方整数，这仍然是一个开放性问题。

综上所述，本文在针对特定且具有加密相关性的整数类别的量子资源效率方面，展示了理论上的突破，证明了对于经典计算机仍具难度的分解问题，实现亚线性空间和深度是可行的。