你真的能忽略Shor算法所需的量子处理步骤数吗？

Question

对问题RSA密钥长度与Shor算法的回答表明，使用Shor算法(需要2n+3量子比特的算法的最著名实现)，例如2048位RSA加密将与4099量子位量子计算机进行小中断。

这是真的吗？如果我的理解是正确的，所需的门(逻辑量子操作)的数目将在log(2^2048)^2×log(log(2^2048))×log(log(log(2^2048)))附近，大约为2.9×10⁷。考虑到即使是经典的计算机也无法使用单个输入数据执行2.9×10⁷门的任何操作，因此假设这么多的门可以在非平凡的时间内由量子计算机操作，实在是没有意义的。

我假设量子计算机要执行一步，执行Shor算法需要(逻辑上)一个输入通过所有这些门，这类似于经典计算机执行足够的计算机代码，通过2.9×10⁷门传递一个2048位输入。因为信息的传播速度不能超过光速，而且门有非零维，所以这不可能在琐碎的时间内发生。如果你在量子计算机中使用光子作为量子比特，不管制造能力如何，波长很可能会为一个栅极设定最小尺寸。

如果您需要在门之间进行任何错误纠正，这将需要额外的空间，因此也会增加延迟。

另外，如果我的理解是正确的，要用Shor的算法计算大的数字，你需要使用经典的计算机来产生一个随机猜测，然后Shor的算法会使用这个猜测来发出数据，可能需要计算这些因子。对于2048位RSA中使用的保理数，平均需要多少猜测？

Has研究了一台大型物理量子计算机的潜在实际运行时，试图执行Shor的大数分解算法？这是否真的支持这样的解释:不管数字的大小如何，您都可以忽略处理时间吗？

Answer 1

我假设量子计算机要执行一个步骤，执行Shor算法需要(逻辑上)一个输入通过所有这些门

你误解了用门运算来测量什么，量子计算机不会有2.9 \times 10^7门(而且所有的数据都是通过这组门反复设置的)。

相反，量子计算机需要执行所有的2.9 \times 10^7门操作；显然，没有必要同时执行它们(事实上，对于Shor，我们不能这样做，因为禁止克隆定理禁止产生量子位元的副本以发送到独立的门，而且更实际的原因是，某些门操作的输入依赖于以前的门操作)。

至于如何将这些2.9 \times 10^7门操作映射到硬件门，我们很难有2.9 \times 10^7物理门；一些硬件门可能在计算过程中被多次重用(就像经典计算机执行D5操作时，相同的门被重用以实现各种模块化的乘法操作)。

如果您需要在门之间进行任何错误纠正，这将需要额外的空间，因此也会增加延迟。

是的，我们知道；上面的2.9 \times 10^7数字反映了逻辑量子位；这将转化为更多的物理量子位元--增加的大小将取决于所使用的量子纠错码(这将取决于物理量子位运算的实际错误率)。

对于2048位RSA中使用的保理数，平均需要多少猜测？

以极高的概率，一个。量子计算机查找g模n的顺序，即g^x \equiv 1 \bmod n所在的值x。除非g相对于p和q (素因子)的排序都是异常小的(如果随机选择g，则只能以极小的概率显示这一点)，否则x的值可以用于快速因子。