例如，如果我在4量子比特的量子超级计算机上使用Shor算法，那将花费一半的时间吗？将1024位RSA分解为常规2位超级计算机？然后，如果我们向上扩展到8量子位超级计算机，直到512量子位，1024量子位，甚至2048量子位等。通过增加更多的量子位，您将得到什么样的分解速度？我本来以为量子计算机只能有4个量子位。但是现在看来，在技术上，您可以继续添加所需数量的qubit。这是否意味着如果我拥有1024 qubit超级计算机，就可以在一瞬间分解RSA 1024位？它可以什么速度检查可能的因式分解？
所以我很感兴趣“理论上”要花多长时间：
蛮力找到了使用Shor算法的1024位加密RSA消息。
用格鲁弗算法通过蛮力找到256位AES加密消息的密钥。
找到SHA2-512位哈希的原映像。 >构造一个用于SHA2-512位哈希的Rainbow表。
如果人们现在将2048位RSA作为标准配置，将花费上述时间的两倍吗？
关于如何计算的一些解释以及花费数秒，数分钟，数小时，数天或数年的时间进行细分将非常值得赞赏。
#1 楼
添加更多的量子位不会增加计算速度。具有4个量子位的量子计算机不会比具有2个量子位的量子计算机更快地分解。量子位是量子计算机的“内存”。更多的量子比特意味着您可以分解更大的数字。如果我没记错的话，您需要叠加$ \ Theta（N ^ 2）$项，这意味着$ \ Theta（\ log（N ^ 2））$个量子位要分解为N。Shor's的运行时间算法是$ O（（\ log N）^ 3）$分解$ N $。要记住的重要一点是，Shor的算法只能分解（通过解决离散对数问题）。请参阅Wikipedia上有关Shor算法的条目。
对于Grover算法，它在“黑匣子”查询方面比传统计算机具有二次优势。因此，量子计算机可以在$ O（\ sqrt {N}）$试验中执行蛮力攻击，而经典计算机则需要$ O（N）$试验。同样，增加量子位的数量不会减少运行时间，但是会增加量子计算机的“内存”。为了运行Grover的算法对密钥进行暴力破解，您需要所有密钥的叠加，这需要$ \ log K $量子位，其中$ K $是可能的密钥数量。
评论
$ \ begingroup $
“ Shor的算法只能分解（通过解决离散对数问题）...”我对此感到困惑。
$ \ endgroup $
– pg1989
13年8月23日在17:21
$ \ begingroup $
Shor的算法包括两部分，一是经典部分，一是量子部分。量子部分执行以下操作：给定$ a $和$ N $使得$ gcd（a，N）= 1 $，找到$ r $使得$ a ^ x = a ^ {x + r} \ mod N $对于所有$ x $。这是使用量子傅立叶变换完成的。经典部分使用此$ r $分解$ N $，即，它减少了分解为离散对数问题的问题。
$ \ endgroup $
– Philippe Lamontagne
13年8月23日在19:05
$ \ begingroup $
@PhilippeLamontagne：实际上，在实践中，增加qubit的数量通常确实会提高Shor和Grovers的实际速度-并不是因为它可以帮助那些算法本身，而是增加附加的辅助qubit可以更快地实现子例程（模块化这些算法所依赖的Oracle乘法）。
$ \ endgroup $
–雨披
18年8月26日在22:51
#2 楼
使用1024量子位的量子计算机，您无法破坏您提到的任何算法。当前对格罗弗（Grover）算法用于AES的实现的估计需要更多的量子位。根据Grassl等人的论文。 AES-256所需的qubit数量为6681，请参见下面的提取表：它的内部状态要大得多，并且说1024量子位还不够。请参见下面摘自本文的图像：
其中澄清了需要2048个量子位来分解1024个RSA密钥。
正如user1147688在评论中指出的那样，本文讨论了逻辑量子位，并指定了：宽容的量子计算技术是必要的。然后，我们的每个“逻辑”量子位必须被编码为几个物理量子位（可能是几十个），逻辑量子门将由许多物理量子位组成。
使目标量子位达到目标将RSA-1024的破坏程度大大高于理论2048。
Edit1：考虑到user1147688的评论
评论
$ \ begingroup $
只是为了澄清C时间值：“右列粗略显示了C的倍数所必需的经典计算资源，而C在今天几乎是不可能的。”自从该论文写于2008年以来，这意味着使用2008年的技术可以实现的目标。而现在我们已经有9年了...
$ \ endgroup $
–not2qubit
17年2月3日在12:49
$ \ begingroup $
此外，第二篇论文中的评论指出：“对于大规模量子计算，似乎非常有必要进行纠错或完全容错的量子计算技术。然后，我们每个“逻辑”量子位都必须是编码成几个物理量子位（可能是几十个），逻辑量子门将由许多物理量子位组成。”
$ \ endgroup $
–not2qubit
17-2-3在12:52
#3 楼
假设还可以将每个量子运算的错误率降低到0.01％以下，那么有可能在大约10天的时间内执行2048位数字分解。
约为5×108离子。
来自：微波阱离子量子计算机的设计图
作为比较：“ RSA Labs声称（请参阅：http://www.rsa.com/rsalabs/node.asp?id=2004），使用NFS破解2048位密钥的难度是2 ^ 32（是32的幂的2）是1024位密钥。2 ^ 32 = 4,294,967,296或将近43亿，因此（使用相同的标准桌面处理）破解DigiCert 2048位SSL证书所需的时间比使用1024位密钥的时间长约43亿倍。因此估计，要打破DigiCert 2048位SSL证书，标准的台式机计算能力将需要4,294,967,296 x 150万年。”
来自：https://www.digicert.com/TimeTravel/
#4 楼
一个额外的答案基于@jhegedus的蓝图文章中的以下引用。 >基于相同的方案，我们可以对解决相关的难题（例如2048位的Shor因数）的机器的系统大小和处理时间进行定量估计。数。为了进行计算，我们假设单量子位栅极时间为2.5μs，两个量子位栅极时间为10μs，离子分离和穿梭时间各为15μs，静态磁场梯度上升和下降时间为5μs。每次测量时间为25μs，因此总的纠错周期为235μs。根据这些数字，执行2048位数字的Shor因式分解将需要110天左右的时间，并且需要2×109捕获离子的系统大小。 Shor分解1024位数字将需要14天左右的时间。这两个分解都将需要几乎相同数量的物理qubit，因为对于2048位和1024位分解，辅助qubit生成所需的速度是相同的。
Trapping 2×109 ions will require 23 × 23 vacuum chambers occupying an area of ca. 103.5×103.5平方米。评论
$ \ begingroup $
我想那还是比LHC便宜。 100个真空室....
$ \ endgroup $
– jhegedus
17-2-4在10:27
评论
评论不作进一步讨论；此对话已移至聊天。您不能只继续添加qubit。每个量子位都需要与其他量子位纠缠在一起（至少要具有完整的通用QM），因此每个量子位都可以大大提高机器运行所需的精度。量子退相干的每个单个实例都需要重新开始计算。