论文摘要列出了一些假设：
我们显着降低了分解整数的成本并结合Griffiths-Niu 1996，Zalka 2006，Fowler 2012，Eker-Hstad 2017，Eker 2017，Eker 2018，Gidney-Fowler 2019，Gidney 2019的技术，在量子计算机上计算有限域上的离散对数。大规模超导量子位平台使用合理的物理假设进行的构造：具有最近邻连通性的量子位平面网格，物理门错误率$ 10 ^ {-3} $，表面代码循环时间为1微秒，反应时间为10微秒。我们考虑了通常被忽略的因素，例如噪声，重复尝试的需求以及计算的时空布局。当将2048位RSA整数分解时，我们的构造的时空量比早期工作的可比估计要小一百倍（Fowler等，2012； Gheorghiu等，2019）。在抽象电路模型中（忽略蒸馏，路由和纠错产生的开销），我们的构造使用$ 3n + 0.002n \ lg n $逻辑量子位，$ 0.3n ^ 3 + 0.0005n ^ 3 \ lg n $ Toffolis和$ 500 n ^ 2 + n ^ 2 \ lg n $测量深度可分解$ n $位RSA整数。我们对有限域中的RSA和基于DLP的方案的密码学含义进行了量化。
设计具有这些特性的量子计算机将如何可行？ 2000万个量子位显然比现在的任何通用量子计算机都多得多，但该论文还指出，这些量子位仅需要最近的邻居连接，这要简单得多。
#1 楼
我是该论文的作者之一。为了使该论文更易于理解，我们将每项主要的优化都纳入了自己的论文。这些子论文共有3个，它们各自独立，彼此独立。
“近似编码置换和分段量子加法器
”。我们在寄存器的各个位置放置了少量填充，以便我们可以分段执行加法运算，并且还可以避免将模整数归一化为[0，N）范围，直到计算结束。为了在量子上下文中应用这些操作，我们必须解决一些信息泄漏问题，这些问题导致填充的表示近似，但是，这是已知的标准经典技术（例如，在GMP中称为“钉子”） 。
使用这些近似表示的模加法要比使用正常表示的模加法器有效得多。例如，当目标是整个算法的总近似误差率为0.1％时，这里是每个加法的时间*空间的比较。 “跑道”条目是使用近似表示的条目。在整个寄存器大小范围内，跑道条目都显着更好：
“窗口量子算术”。传统上，如果您知道在生成物理乘法电路时将乘以哪个常数，则可以将电路专门化为该因子。这使您可以使电路更小，更高效。有一个等效于此优化的量子，其中可以使用要乘以的经典常数的知识来优化量子程序。我们使用它使n位量子经典乘法程序的log（n）倍缩短。
然后，我们对该技术进行概括，将其同时应用于电路的幂运算部分，并节省log（n）的另一个因数。我们在撰写本文时实际上并不知道，因此在当前版本中未引用。）
“使用AutoCCZ状态进行表面代码计算的灵活布局”。到目前为止，这是最量子力学的知识，所以我将不尝试解释其细节。您可以将其视为找到一种更好的方法来打包计算，减少路由数据时使用的空间开销，并允许其以受传统控制系统反应时间（而不是错误校正代码）限制的速率进行距离。
实际上，这里的主要贡献可能是说布局是什么，而不是抽象地讨论布局。我们有一个操作区域，其中，带有波纹的加法之字形在水平方向上来回移动，而输入数据则通过垂直方向流过，并且随着数据的处理，操作区域逐渐移动。 （从上到下的行）随时间（从左到右）：
少量时间内的二维数据布局的模拟快照：
本文中的思想基于Fowler从2012年开始的工作。在本文中，但它们并不是全新的（它们是建立在以前的工作基础上的），并且它们之间没有强烈的耦合（如果其中一个是错误的，其他的将仍然存在）。因此，我认为节省下来的钱会很稳固。我更担心的是人们是否能够构建具有20M量子比特的量子计算机，而不是我估计的数字降低了2倍。
评论
$ \ begingroup $
这很有趣，我当然需要阅读您所链接的论文，但是我最好奇的是用摘要中描述的属性构建量子计算机的可行性。我的非专家理解是，与具有最近邻居连接的最大量子计算机的数量级为50量子比特相比，它目前相距遥远，但是我可能会错。
$ \ endgroup $
–森林
19年6月8日在1:56
$ \ begingroup $
@forest是的，资源需求远远超出了任何人现在可以做的任何事情。
$ \ endgroup $
– Craig Gidney
19年6月8日在17:52
$ \ begingroup $
如果我理解正确，那么这项工作的价值是：随机硬件错误导致量子计算的未来不太可能
$ \ endgroup $
– kelalaka
19/12/9在21:03
$ \ begingroup $
@kelalaka很难解析您的问题，但是本文明确地涉及在考虑和纠正噪声的情况下进行计算。我们使用的纠错码是表面码。表面代码在arxiv.org/abs/1208.0928中进行了详细说明。我对您链接的文章的看法是，这完全是错误的。我们知道，从90年代开始，原则上就可以进行量子误差校正，尽管硬件仍然不够好，无法检查它在实验中是否确实有效。找出它并不是一个巨大的发现。
$ \ endgroup $
– Craig Gidney
19/12/9在21:29
$ \ begingroup $
对不起，不清楚。我认为除了普通的量子误差校正以外，还有更多的东西。这些东西到处都是新闻站点。现在，经过仔细思考，它们要么表明与QEC无关的内容，要么正如您所说的是不正确的。
$ \ endgroup $
– kelalaka
19/12/9在21:36
评论
相关讨论：news.ycombinator.com/item?id=19998004要了解构建量子计算机的困难，最好观看约翰·马丁尼斯（Google / UCSB团队负责人）关于量子分解机的前景的受邀演讲。
@J.P。我知道用约5000个逻辑完全重叠的量子位创建系统的困难（这是Shor算法所必需的），并且知道这远远超出了任何人现在可以做的事情，但是最近的论文提出了一种使用量子位来完成此任务的方法更容易使用。具有近邻连通性的2000万个（物理）量子位比完全重叠的甚至约5000个逻辑量子位更容易实现。
你看过视频吗？约翰·马丁尼斯（John Martinis）还谈到了物理量子位（以及错误率等）以及如何使用它们。