本文的RSA 2048与噪声量子位分解的技术是否符合实际？

Question

一篇题为2048位RSA整数在8小时内如何使用2000万个含噪量子位的论文刚刚发表，该论文提出了一种以2048位为模数对RSA密钥进行因素分析的技术，其设计所强调的假设是现实的。这项新研究的意义是什么？

这份文件的摘要列出了一些假设：

我们通过将Griffiths、Zalka 2006、Fowler 2012、Eker 2017、Eker 2017、Eker 2018、Gidney-Fowler 2019、Gidney 2019、Gidney 2019和Gidney 2019的技术相结合，大大降低了计算有限域上整数和离散对数的成本。我们使用大型超导量子比特平台的合理物理假设来估算我们的建造成本:具有最近邻连通性的平面量子比特网格、10^{−3}的特征物理门错误率、1微秒的表面编码周期时间和10微秒的反应时间。我们考虑了通常被忽略的因素，如噪声、重复尝试的需要以及计算的时空布局。当分解2048位RSA整数时，我们的构造的时空体积比早期工作中的可比估计少100倍(Fowler等人)。2012年，Gheorghiu等人。2019年)。在抽象电路模型(它忽略了蒸馏、路由和纠错的开销)中，我们的构造使用3n+0.002n\lg n逻辑量子位、0.3n^3+0.0005n^3\lg n托福奥利和500n^2+n^2\lg n测量深度来计算n-bit RSA整数。我们量化了我们的工作对RSA和基于有限域DLP的方案的密码含义。

如何设计一台具有这些特性的量子计算机?2000万量子位显然比目前任何通用量子计算机都要大得多，但本文也指出，量子比特只需要最近邻连通性，这就简单多了。

Answer 1

我是这篇论文的作者之一。

为了使论文更加平易近人，我们将每一个主要的优化因素都考虑到了它自己的论文中。有三个子论文，它们各自独立地站在一起，基本上独立于其他文件。

1. “近似编码排列和分段量子加法器”。我们在寄存器中的不同位置放置少量填充，以便能够以分段方式执行加法操作，并避免在计算结束前将模整数规范化到[0，N]范围内。为了在量子上下文中应用这些操作，我们必须解决一些信息泄漏问题，这些问题导致填充的表示是近似的，但否则这是一种已知的标准经典技术(例如，它称为GMP中的“钉子”)。使用这些近似表示的模块加法比使用正规表示的模块加法显着地提高了效率。例如，下面是针对整个算法的0.1%的总逼近错误率时，每个加法的时间*空间的比较。“跑道”条目是使用近似表示的条目。在整个注册范围内，跑道条目明显更好：

这些表示建立在以前工作扎尔卡从2006年开始的基础上。

1. 加窗量子算法。经典地说，如果你知道在产生物理乘法电路时你要乘以什么常数，你可以把电路专门化到这个因子上。这让你可以使电路更小，更高效。有一个量子等价于这个优化，其中量子程序可以优化使用经典常数的知识，你要乘。我们利用它使n位量子经典乘法程序log(n)缩短一倍.

然后我们推广了这一技术，同时将它应用于电路的指数部分，并保存了log(n)的另一个因子。本文基于R. Van Meter 2005年以前的工作 (虽然我们在撰写论文时并不知道这一点，所以在当前版本中没有引用)。

1. “使用AutoCCZ状态的表面代码计算的灵活布局”。到目前为止，这是量子力学中最重要的一个，所以我不会试图解释细节。您可以将其看作是找到一个更好的方法来打包计算，减少数据路由时所使用的空间开销，并允许其以受经典控制系统反应时间限制的速度前进，而不是由纠错代码距离所限制。这里的主要贡献可能实际上是首先说明布局是什么，而不是仅仅抽象地谈论它。我们有一个操作区域，当输入数据流垂直通过时，波纹进位加法在水平上来回移动，并且操作区域随着数据的处理而逐渐移动。数据的位置(从上到下)随着时间的推移(从左到右)：

在一小段时间内模拟2d数据布局的快照：

本文的思想建立在2012年福勒年以前的工作的基础上。

总之，论文中有很多想法，但它们并不是全新的(它们建立在以前工作的基础上)，它们也不是很强的耦合(如果其中一个是错误的，其他的将仍然有效)。所以我认为节省的钱是相当稳固的。我更担心的是，人们是否能够制造出2000万量子位的量子计算机，而不是我估计的2倍。