Formally verified harness for Shor's order finding algorithm with gate cost
本文提出了一种经过形式化验证的测试框架,该框架能够摄取来自外部来源(如 AI 智能体)的递归电路设计策略,从而自动生成关于 Shor 阶数寻找算法在数学正确性及 门成本缩放方面的机器检查证明,进而为发现具有保证正确性的更高效量子分解电路提供一个开放性挑战。
原始论文采用 CC BY 4.0 许可(http://creativecommons.org/licenses/by/4.0/)。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性,请参阅原始论文。 阅读完整免责声明
在现代计算的领域中,存在着一种计算速度与秘密安全性之间的根本性张力。几十年来,数字通信的安全一直依赖于一种数学锁:将一个大数分解为两个质数构建块的难度。虽然经典计算机在处理这项任务时非常吃力,破解单个代码可能需要数千年的时间,但基于量子物理定律构建的理论机器可以在几分之一秒内解决这个问题。这种潜在的威胁促使科学家们不断完善这种机器的设计蓝图,特别是被称为 Shor 算法的特定算法。挑战从未在于该算法在理论上是否可行,而在于如何构建能够高效运行它的物理机械。瓶颈在于算术运算:量子系统中进行乘法和除法所需的特定步骤。多年来,这些步骤中最有效的已知方法所要求的操作数量随数字规模增长得如此之快,以至于即使是最强大的未来计算机也可能没有足够的资源来执行该任务。
一组研究人员现在推出了一种旨在导航这一复杂设计空间的新框架,提供了一种寻找更快、更高效电路的方法,同时保证数学上的正确性。他们将他们的创造物称为 ForShor,这是一个形式化验证的护栏,既充当裁判又充当构建者。他们并没有要求科学家手动构建量子电路的每一种可能变体——这是一项容易出错且无法彻底检查的任务——而是构建了一个系统,研究人员可以提交一套规则,或者说一种“策略”,来描述乘法应该如何被分解。随后,系统会自动根据严格的数学标准对这些规则进行检查。如果规则通过,系统就会生成一个完整的、经过验证的量子程序,并精确计算出运行它需要多少个物理组件,即门(gates)。这种方法允许进行更优设计的开放式搜索,让人类专家和人工智能代理可以在其中竞争寻找最有效的路径,同时系统确保生成的电路在数学上是可靠的,并能进行实际的资源估算。
问题的核心在于算法如何处理乘法。为了分解一个大数,量子计算机必须执行一系列大规模的乘法。研究人员专注于一种称为递归 Toom-Cook 乘法的技术,其工作原理类似于一种复杂的长除法。该方法不是直接将两个大数相乘,而是将它们拆分为较小的块,对这些块进行乘法运算,然后重新组合结果。这个过程的效率完全取决于这些块是如何划分以及结果是如何重新组装的。排列这些步骤的方法有无数种,从而产生了一个巨大的设计空间。研究人员发现,虽然存在一种精确的数学方法可以找到绝对最佳的排列方式,但在处理现代密码学中所使用的数字规模时,该方法在计算上是不可行的。可能性的数量如此庞大,以至于即使使用最快的超级计算机,检查每一个选项所需的时间也会超过宇宙的年龄。
为了解决这个问题,该团队创建了一个将设计电路的创造性工作与验证工作的繁琐工作相分离的系统。参与者的挑战在于提交一个“策略”,这本质上是一套指令,告诉计算机如何拆分数字以及在每一步执行什么操作。随后,系统会检查这些指令是否遵循一套严格的逻辑规则。这些规则确保了步骤是可逆的,没有信息丢失,并且最终结果在数学上等同于预期的乘法。如果策略通过了检查,系统会自动构建完整的量子电路并计算其资源成本。这一过程是以形式化的方式进行的,不留任何疑点;系统证明了任何有效的策略都会产生正确的结果,无论设计者是谁,也不论设计多么复杂。
研究结果具有重要意义。通过允许在无需担心引入错误的情况下继续寻找更好的设计,研究人员已经证明,减少 Shor 算法所需的运算量是可能的。他们的分析表明,通过正确的设计选择,运算量的增长速度可以比之前认为的要慢得多,从三次增长率转变为接近二次增长率。这意味着对于非常大的数字,这种新方法所需的资源可能远少于标准方法。然而,研究人员谨慎地指出,尽管理论上的改进是实质性的,但目前最好的设计仍然需要远超现有技术的物理组件数量。对于目前加密中使用的规模之大的数字,系统估计,最有效的已知设计仍需要超过一万亿次特定的操作,即 T 门。
该项目还凸显了人工智能时代科学研究的一种新方式。该框架被设计为一个开放式挑战,邀请人类研究人员和人工智能代理提交自己的设计。系统作为一个中立的裁判,接受任何符合数学标准的提交,并拒绝不符合标准的提交。这创造了一个安全的创新环境,通过机器检查的验证消除了设计缺陷的风险。研究人员发现,即使在一个受限的设计选择集中,寻找最优解也是极其困难的。他们使用一个涉及 2048 位数字(这是加密中常用的尺寸)的具体示例测试了他们的系统。系统确认,虽然在理论上存在一个精确的最优解,但通过暴力破解找到它是无法实现的。相反,该系统允许启发式搜索,即智能代理可以探索设计空间并提出更好的解决方案,而这些方案随后会被立即验证。
一个关键发现是,算法的效率在很大程度上取决于被分解数字的大小。研究人员发现,拆分数字的最佳方式会随着数字变大而改变。适用于较小数字的设计对于较大的数字可能会效率低下。他们的系统可以通过在计算的不同阶段允许不同的拆分策略来处理这个问题。这种灵活性对于突破可能的极限至关重要。团队将他们的结果与之前的方法进行了比较,发现他们的方案在运算量方面提供了明显的优势,但仅限于数字显著大于当前使用的数字时。对于标准的 2048 位数字,虽然存在改进,但尚未足以使该任务在近期技术下变得可行。
这项工作还架起了抽象数学证明与实际工程之间的桥梁。系统将经过验证的电路数学描述转化为可以被用于估算运行算法所需物理资源的软件工具的格式。这种转换是至关重要的一步,因为它允许研究人员准确看到在真实机器上运行该算法需要多少个量子比特(qubits)以及多少个纠错组件。研究人员利用这一流水线生成了各种场景下的详细估算,证实了理论上的改进在转化为具体的资源计数时依然成立。他们发现,运算量的增长方式是可预测的,遵循着他们所证明的数学模式。
尽管取得了进展,研究人员也承认仍有大量工作要做。目前的估算基于理想化的量子计算机模型,而现实世界的硬件会引入额外的挑战,例如噪声和纠错的需求。该系统尚未考虑机器的物理布局以及在处理器不同部分之间移动信息所需的时间。这些是该领域的下一个前沿。然而,能够在搜索最有效设计的同时对算法的正确性进行形式化验证,是向前迈出的重要一步。它提供了一个坚实的基石,让未来的改进得以建立在其之上,确保每一个新想法都经受住最高标准的数学严谨性检验。
该项目是量子软件工程新时代的概念验证。通过将形式化验证与开放式自动化搜索相结合,研究人员创建了一个能够处理量子算法复杂性的工具,而这在以前是不可能的。这种方法不仅加速了对更好算法的搜索,同时也建立了对结果的信任,因为每一项主张都有机器检查的证明作为支撑。随着量子计算领域的不断演进,此类工具对于在广阔的设计空间中导航,并将理论上的可能性转化为实际现实将是必不可少的。研究人员已向公众开放了他们的框架,邀请全球社区共同寻找分解大数的最有效方式,这一任务仍然是该领域最重要的挑战之一。
您所在领域的论文太多了?
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要,使用您的语言。