用量子计算机分解2048位整数？

Question

在这的论文中，有一个抽象的陈述：

我们的构造使用3n + 0.002n \log(n)逻辑量子位、0.3n^3 + 0.0005n ^3\log(n)托福奥利和500n^2 +n^2 \log(n)测量深度来考虑n位RSA整数。

本文的标题是使用20.000.000个量子位来破解RSA-2048，其中介绍性 -also指的是pg.22中包含的表，该表将RSA-2048映射到6189个量子位。

我的问题是:量子计算机的发展需要考虑的数量是多少？换句话说，根据本文，量子计算机破解RSA-2048所必需的量子位数是多少? 6189或20.000.000？

此外，逻辑量子位、噪声量子位、测量深度和托菲利的定义对于理解这一概念也是非常有用的。

Answer 1

20,000,000是一定质量的物理量子位数，与目前正在开发量子器件的工程队所引用的量子位数最接近。然而，量子计算能力并不仅仅取决于可用量子位的原始数量。所引用的20,000,000量子位需要能够在1微秒内以99.9%的精度执行一个量子计算门，与大量邻近的量子位进行交互，并保持一个量子态数个小时。不同的设备离实现这一规范有多近，这将是不同的，我们必须深入研究细节。工程师有可能生产出比本规范性能更好的量子位元，在这种情况下，所需的量子位数就会更少。

一个逻辑量子位应该被认为是一个理想的计算资源，它以完美的保真度执行门，可以自由地与其他逻辑量子位进行通信，并且可以无限期地保持它的量子状态。所需的6189个逻辑量子位实际上不可能通过改进的工程来减少，但是可以通过改进的算法来还原。

通过使用量子纠错码来纠正门执行中的错误和随着时间的推移而丢失信息，逻辑量子位的某些功能可以由物理量子位集合来模拟。这些噪音/物理量子位元可以通过不同的方式来实现(大多数主要的工程项目都使用超导量子位元)，所有这些都有可以通过工程加以改进的局限性。在算法的持续时间内，模拟逻辑量子位所需的物理量子位数取决于物理量子位的质量。仿真本身也增加了计算负担。

测量深度是量子信息为执行算法而必须通过的门的最长路径。算法的复杂度将取决于量子位数和测量深度。两者的乘积是衡量这一复杂性的一个粗略的整体尺度。

Toffoli门是一种基本的门，它可以构造非常一般的量子电路(类似于Shannon定理允许我们从NAND门构建通用计算电路)。从工程的角度来看，它通常是最难实现的基本门，因此，Toffoli门的数量是衡量工程挑战的另一个标准。在经典数据上，Toffoli门将三个输入位(a,b,c)发送给三个输出位(a,b,c\oplus a\cdot b)。