⚛️ quantum physics

From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

本文针对 N=15 的情况，在真实的 NISQ 硬件上对 Shor 算法与 Regev 算法的量子分解算法进行了实验对比，分析了它们在算术编码方面的不同结构化方法如何与设备噪声及采样限制相互作用，从而为替代分解策略的实际基准测试提供参考。

原作者： Daniela Falcó, Arturo Rodríguez, Guillermo Rivas, Ricardo S. Alonso

发布于 2026-06-17

📖 1 分钟阅读🧠 深度阅读

原作者： Daniela Falcó, Arturo Rodríguez, Guillermo Rivas, Ricardo S. Alonso

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

大局观：破解密码的两种不同方式

想象一下，你正试图使用一种被称为量子计算机的新型超级计算机来破解一个秘密代码（分解一个数字）。长期以来，大家一直使用由数学家**秀尔（Shor）**发明的一种特定方法。这就像是破解密码的“金标准”食谱。

然而，目前的量子计算机就像是“嘈杂”的厨房。它们规模很小，容易出错，而且很容易产生混乱。因此，科学家们正在寻找可能在这些混乱条件下表现得更好的替代食谱。其中一种新的食谱是由数学家**雷格夫（Regev）**发明的。

这篇论文是一项实验，作者在真实的、有噪声的量子计算机上同时烹饪了这两种食谱（秀尔的和雷格夫的），以观察哪一种在处理“噪声”方面表现得更好。他们并没有尝试破解一个巨大的、现实世界的代码（那可能需要数年时间）；相反，他们破解了一个微小的、简单的数字（15），仅仅是为了观察这两种方法的行为表现。

两种食谱：“手电筒”与“雾中的地图”

为了理解其中的区别，请想象你正试图在一个黑暗的房间里寻找隐藏的宝藏。

1. 秀尔算法：手电筒

工作原理： 秀尔的方法试图将一束非常明亮、锐利的手电筒光照射在宝藏上。它将所有的能量集中在这一两个特定的点（波峰）上。如果光线足够亮，你就能立即看到宝藏。
问题所在： 在嘈杂的厨房里，手电筒的光会闪烁。如果光线变得太暗或过于摇晃，你就无法再辨认出宝藏的位置。那个“锐利的波峰”会变得模糊，信号也会随之丢失。
论文的发现： 在 IBM 的计算机上（噪声稍小一些），手电筒仍然可以正常工作。但在 QMIO 计算机上（噪声更大），光线变得过于模糊，以至于他们找不到宝藏了。

2. 雷格夫算法：雾中的地图

工作原理： 雷格夫的方法不使用单一的手电筒。相反，它在地图上投射出许多虚线点。没有任何一个单独的点直接指向宝藏，但如果你观察所有点组成的整体模式，它们就会形成一个揭示位置的形状。它将信息分散在许多点上。
问题所在： 在嘈杂的厨房里，雾气会变得更浓。地图上的点会变得散乱且混杂。由于信息是分散的，当噪声干扰时，就很难看清这种模式。
论文的发现： 雷格夫的方法创造了一个更“平坦”的点分布。在噪声较大的 QMIO 计算机上，这些点变得极其散乱，导致模式完全消失了。

实验过程：发生了什么？

研究人员在两台不同的量子计算机（IBM 和 QMIO）上运行了这两种“食谱”，并将它们与完美的、无噪声的模拟进行了对比。

“理想”世界： 在完美的模拟中，秀尔的方法显示出几个非常高且锐利的尖峰（手电筒）。雷格夫的方法则显示出一些在模式中略微较高的散落点（地图）。两者都完美运行。
“现实”世界（IBM）：
- 秀尔： 尖峰变得稍微宽了一些、矮了一些，但你仍然能看到它们。虽然“手电筒”在摇晃，但依然可见。
- 雷格夫： 点变得更加散乱，但仍有几个点比其他的稍微高一点。虽然“地图”起了雾，但模式依然隐约可见。
“现实”世界（QMIO —— 噪声更大的机器）：
- 秀尔： 尖峰完全变平了。手电筒熄灭了。计算机无法区分信号和噪声之间的区别。
- 雷格夫： 这些点变成了一片均匀的云团。模式完全消失了。这张“地图”雾气太重，看起来就像随机的静电噪声。

核心结论

论文得出结论：目前还没有哪种方法是明显“更好”的，对于这些小型、有噪声的机器而言。

秀尔的方法像是一种高精度工具：如果环境洁净，它表现极佳，但如果有一点点脏东西（噪声），它就会轻易损坏。
雷格夫的方法像是一个分布式网络：它使用的电路更浅（步骤更简单），这听起来不错，但因为它将信息分散开来，噪声同样有效地搅乱了这种模式。

底线：
作者发现，这些算法存储信息的方式有着本质的区别。秀尔“浓缩”信息（像激光一样），而雷格夫“分布”信息（像喷雾一样）。在当今这些有噪声的计算机上，两种策略都面临困难，但它们的失败方式各不相同。秀尔失去了其锐利的焦点，而雷格夫失去了其几何模式。

这项研究并不是说我们现在就能破解银行的真实代码。相反，它告诉我们，随着我们制造出更好的量子计算机，我们需要了解这些不同的算法是如何对噪声做出反应的，以便我们能为合适的机器选择合适的算法。

技术摘要：从周期寻找到格采样

问题陈述
虽然 Shor 算法在理论上能在多项式时间内解决整数分解问题，但在当前的含噪声中型量子（NISQ）硬件上，其实现受到电路深度、门误差和退相干的严重限制。这些局限性促使人们对替代分解算法产生兴趣，例如 Regev 算法，它将问题重新表述为高维格采样任务，而非一维周期寻找问题。然而，现有的实验分析往往缺乏在严格控制条件下的系统性、多后端比较，以理解这些截然不同的算法结构如何与真实的硬件噪声相互作用。本研究通过在真实量子硬件上实验性地比较 Shor 算法和 Re Regev 算法，旨在解决这一空白，以表征它们的相对鲁棒性和失效模式。

方法论
作者使用基准实例 $N = 15$ 进行了受控实验研究。两种算法均使用 Qiskit 实现，并在两个不同的量子后端上执行：位于加利西亚超级计算中心（CESGA）的 QMIO 量子计算机以及 IBM 公开访问量子处理器（ibm_torino）。理想（无噪声）模拟作为参考基准。

算法配置：
- Shor 算法： 使用基数 $a=2$ ，控制寄存器包含 $k=3$ 个量子比特，以寻找阶 $r=4$ 。该电路利用基于置换而非通用算术的专门化、浅层模幂运算构建，以最小化深度。
- Regev 算法： 配置为二维实例（ $d=2$ ），基数为 $a_1=4, a_2=49$ 。它采用了对 $\mathbb{Z}^d$ 上的高斯叠加，随后进行傅里叶采样以逼近对偶格中的向量。
编译与执行： 电路使用 Qiskit 进行转译，参数根据每个后端的原生门集和连通性进行了调整。所有硬件运行均使用了 4,096 次采样（shots）。
评估指标： 为了在不依赖每次运行进行完整经典重构的情况下量化噪声的影响，作者引入了基于分布的指标：
- 香农熵 ( $H(p)$ )： 衡量概率分布的离散程度。
- 有效支持集大小 ( $N_{eff}$ )： 估计对分布有显著贡献的结果数量。
- Top-K 质量 ( $M_4$ )： 四个最频繁出现的结果所包含的总概率份额。

核心贡献

受控实验基准： 本文在相同的题目实例（ $N=15$ ）下，通过多个硬件平台和理想模拟，提供了 Shor 算法与 Regev 算法的直接、底层比较。
多后端评估： 结果涵盖了 IBM 和 QMIO 设备，为不同硬件架构如何影响算法性能提供了见解。
信息编码解释： 研究通过“信息集中”（Shor）与“信息分布”（Regev）的视角来解释实验结果。它展示了这些结构差异如何导致测量直方图中性质迥异的噪声诱导退化。
可复现性： 作者报告了用于生成实验分布的具体算法参数和编译流水线。

结果
实验数据揭示了两种算法在 NISQ 约束下截然不同的失效模式：

Shor 算法（信息集中）：
- 在理想模拟中，概率质量高度集中在极少数频谱峰值上（低熵， $N_{eff} \approx 4$ ， $M_4 = 1.0$ ）。
- 在 IBM 硬件上，分布有所展宽但仍保留主峰（ $M_4 = 0.921$ ），允许在阶恢复方面取得部分成功。
- 在噪声更大的 QMIO 设备上，频谱峰值被显著平坦化并被遮蔽（ $M_4 = 0.564$ ， $N_{eff} \approx 7.8$ ），导致无法提供用于经典重构的周期结构。
- 观察： Shor 算法对相位误差高度敏感；一旦尖锐的峰值被噪声展宽，算法便无法提供有效信息。
Regev 算法（信息分布）：
- 在理想模拟中，其分布本质上比 Shor 算法更分散，但仍表现出一组与对偶格一致的主导向量（ $N_{eff} \approx 2.34$ ， $M_4 = 0.944$ ）。
- 在 IBM 硬件上，分布变得更加弥散（ $M_4 = 0.645$ ），但仍有一部分结果足够占优，足以潜在地支持格规约。
- 在 QMIO 上，几何信号被强烈稀释（ $M_4 = 0.29$ ， $N_{eff} \approx 15.8$ ），概率质量均匀地分布在许多向量上，有效地遮蔽了格结构。
- 观察： Regev 算法依赖于多个相关样本的统计偏差。尽管其编译后的电路深度更浅（表 2 显示 Regev 在两个平台上的编译深度均低于 Shor），但多维采样阶段引入的噪声敏感性导致几何信号迅速扩散。
电路深度与鲁棒性： 尽管 Regev 算法具有更浅的编译电路深度（例如在 IBM 上为 147 对比 210），但这并未转化为在当前硬件上更优的鲁棒性。在噪声作用下，Regev 的测量分布比 Shor 扩散得更快。

意义与主张
本文谦逊地指出，在当前的 NISQ 设备及小规模 $N$ 范畴（ $N=15$ ）内，两种算法均未表现出明显的实际优势。相反，研究强调了一个根本性的权衡：

Shor 算法 在噪声较低时受益于高度结构化、集中的输出，但在相位相干性丢失时会发生灾难性失败。
Regev 算法 将信息分布在高维空间中，这可能为更大规模的问题提供不同的缩放特性，但目前在多维采样过程中面临着更高的噪声敏感性。

作者总结认为，这些结果强调了通过实验基准测试来理解算法设计选择之实际意义的重要性。他们强调，在容错设置下的渐近关系并不保证在 NISQ 硬件上表现出相似的行为，因为在 NISQ 环境下，算术信息的特定编码方式（集中 vs 分布）决定了噪声如何显现以及算法如何失效。未来的工作拟将这些基准测试扩展到更大的 $N$ ，并探索针对这些特定权衡的误差缓解策略。

大局观：破解密码的两种不同方式

两种食谱：“手电筒”与“雾中的地图”

实验过程：发生了什么？

核心结论

技术摘要：从周期寻找到格采样

类似论文