论文分享｜Shor算法首次取得质的突破

论文名称：An Efficient Quantum Factoring Algorithm

论文链接：https://arxiv.org/abs/2308.06572

1

背景介绍

1994年，彼得·肖尔(Peter Shor)创造了量子计算机的第一个实际用途：入侵互联网。

Shor是麻省理工学院(MIT)的一名应用数学家，他展示了量子计算机在寻找大数的素数因子方面如何能比经典计算机快出数倍。这些素数被用作密钥，确保互联网上大部分加密信息的安全。

30年来，肖尔(Shor)算法一直是量子计算机前景的一个范例。尽管当前的量子设备还不够大、也不够可靠，无法对大数进行运算。但现在，一位计算机科学家揭示了一种新的量子算法，它可能比肖尔算法更好。

纽约大学的奥德·雷格夫(Oded Regev)在8月12日首次发布在arXiv服务器上的预印本中提出了一种方案，可以大大减少超大型数字因数分解所需的门数或逻辑步骤。原则上，它可以让更小的量子计算机找出加密密钥，或者让更大的机器更快地解码加密密钥。

2

本文贡献

这篇论文的主要贡献是开发了一种基于格的全新量子分解算法，与Shor的算法有根本的不同。Regev的算法的门数量比Shor的算法显著较小，使其更适用于近期量子计算机的实际实现。

此外，该算法依赖于一个与经典分解算法相关但一般情况下未知是否成立的数论启发式假设。该论文还探讨了算法的潜在优化，包括使用量子纠错和更高效的格约简技术。

本文的主要贡献在于，分解一个n位的整数，只需要n^1.5个门即可实现，这也意味着未来RSA加密方案将不再安全。

3

关于论文

理解这篇论文的意义，首先需要对量子计算和数论有基本的了解，具体而言，我们需要熟悉使用量子电路分解整数的Shor算法，以及基于格的密码学和最坏情况到平均情况的约简概念。

与此同时，我们还需要具备基本的线性代数和复杂性理论知识。

Regev算法的高级思想是利用基于格的方法来分解n位整数，使用比Shor算法少得多的量子电路门。该算法首先创建一个量子叠加态，然后使用经典程序计算模整数的某些值的乘积。

这种计算是在叠加态下进行的，使得算法能够高效地同时探索许多可能的值。然后测量得到的量子态，并使用测量结果提取整数的因子信息。该算法的关键在于，使用基于格的方法来减少计算所需的门数量，同时保持必要的量子相干性。

最后，该论文还提供了算法的详细描述，以及对其复杂性和正确性的分析。

3

论文全文

来源：光子盒

分享仅供学习参考，若有不当，请联系我们处理

END

热文推荐