将其应用于密码分析有何用途？
#1 楼
TL; DR：不多。如果量子位的质量很高，某些非常棘手的算法可以使用它们更快地执行某些算法子过程，但实际上数量比质量多。因此，这只是目前的研究。一台50量子位的通用量子计算机可以使用Grover算法在时间$ \ approx7 $的步长上而不是$ \ approx25 $的情况下反转49位函数。乐观地假设，仅需要1位开销来计算函数，就可以采用传统的步骤，加速比为3.5。换句话说，如果要反转许多49位功能，则具有50个量子位的1 GHz量子计算机将类似于3.5 GHz的经典计算机。不那么乐观的是，它将需要25位，但要以2.5的速度处理25位功能。 IMO并不令人兴奋。
一台50量子位的通用量子计算机可以使用带有Griffiths和Niu / Kitaev循环（迭代相位估计）的Shor算法的变体，并带有自适应电路来分解一个49位数字。我不确定这将花费多长时间，但是您可能会使用标准的QFT加教科书，或者可能以这种大小使用Karatsuba乘法，需要大约100,000步。假设是一台时钟不错的量子计算机，那很好，但是一台经典计算机只需用半毫秒就能完成SQUFOF的相同操作，因此尚无密码含义。此处，量子加速大约是15倍。如果没有自适应电路，那么使用Häner，Roetteler和Svore的人将只有24位，这几乎消除了任何量子优势。已经发现一种新的量子分解算法VQF，非常适合这种小型量子计算机。不幸的是，它不能很好地扩展，甚至不能达到经典算法的水平，特别是不能显示量子优势。它能够分解出看似数量众多的数据，但是这需要花费大量的经典工作，如果您使用量子计算机来卸载经典工作，这是没有用的。
一般来说，是50-75 *量子位是量子至上开始变得有趣的地方，量子化学是100-200量子位，数论是1000-2000量子位，密码学是2049-10000量子位。 （诚然，在那之前您会得到一些好东西。）所有这些都是针对高质量的通用量子计算机的。绝热量子计算机和量子退火器很有趣，但除模拟自身外，在其他方面均不胜过经典算法。
从计算过程中出现任何退相干的机率，例如<50％的意义上讲，这假定了非常高质量的qubit。因此，对于Grover的算法，您将需要99.8％的非解串量子比特；对于Shor，您将需要99.99999％的非解串量子比特。如果您无法到达那里，但可以接近，则可以重新运行计算，直到它起作用为止，但是很大的耐心只能弥补一点点质量。如果您无法达到该质量水平，那么传统观点认为您需要将qubit的数量增加至少10-1000倍才能进行纠错。我不知道最新的技术水平，但是Calderbank，Rains，Shor和Sloane有两篇论文。对后者的仔细阅读表明，纠错的最基本形式（单量子位纠错）使用简化的[[85，77，3]]海明码版本“花费”了8个量子位。但是实际上编码它需要辅助量子位，而且我不知道有效地做到这一点的方法。通过Chao＆Reichardt，我知道的最佳方案仅需要两个qubit的辅助函数，但是如果我们可以将[[63，51，3]]汉明码缩短为[[48，36，3]]，则需要12 qubit ，或者如果我们必须使用[[31，21，3]]海明码，则有效地是27（！）量子位。 （汉明代码绝对可以缩短，我只是不知道Chao-Reichardt方法是否可以与缩短的代码一起使用。）因此，采用当前技术，一台50量子位的量子计算机可以用最少的数量模拟21或36量子位。纠错，这取决于我的解释是正确的。如果有人知道更好的方法，请告诉我。
当前的量子计算机已经达到了量子比特数量的低端，但无法获得所需的计算深度所需的质量。 Google的量子至上论文讨论了模拟多达20个深度的过程，需要进行数千万次运行才能将信号与噪声区分开。即使付出很大的努力，也几乎不可能在该机器上运行深度为25的电路。但是将需要成千上万的深度，所以我们还有很长的路要走。仍然有进步！
评论
$ \ begingroup $
我认为50位qbit QC不能在49位函数上使用Grover。 AFAIK，格罗弗的算法要求它检查的内部函数是可逆的，这意味着我们需要将单向函数嵌入到更大的可逆函数中。这是完全可行的，但是这意味着我们需要更多qbit来表示允许其可逆的状态。
$ \ endgroup $
–雨披
17 Mar 7 '17 at 21:11
$ \ begingroup $
@poncho 1位绝对是最好的情况，大多数功能将占用更多qubit。但是，可能有很多有趣的函数可以使用回收和其他技术以相对较少的qubit进行编码。我本可以使用5位中的25位函数，加速比为2.5，来代表更正常的情况。
$ \ endgroup $
–查尔斯
17 Mar 7 '17 at 21:28
$ \ begingroup $
嗯，如果您要为单向函数搜索特定的目标值，则需要在可逆函数中至少有n / 2（在这种情况下为25）个额外的位，以使其有趣。如果您有一个功能，可以用更少的额外位数进行反转，那么传统的计算机可以将所有可能的图像与您要搜索的值以及n / 2个辅助位的各种设置一起反转，并查看哪个可行;无需质控即可获得与Grover相同的性能。
$ \ endgroup $
–雨披
17 Mar 7 '17 at 21:48
$ \ begingroup $
@poncho我一直在寻找这样的下限，但是我在文献中没有找到下界。如果您有参考，请回答，我肯定会赞成。直到今年，我还不知道仅用1 qubit的开销就能完成Shor的工作，而且我认为$ n + 3 $（总$ 2n + 3 $）的性能令人印象深刻，因此我使用了类似的乐观的1 qubit对于格罗弗。
$ \ endgroup $
–查尔斯
17 Mar 7 '17 at 22:14
$ \ begingroup $
实际上，我只是在仔细考虑。如果您有一个使用$ n $ postimage位（已知，这就是您要查找的图像）和$ k $“ helper”位（使该函数可逆）的逆函数，则可以扫描$ 2中的所有可能性^ k $在传统计算机上花费的时间（并挑选出有效的计算机）；这将使您获得单向函数的逆函数。如果$ k
–雨披
17年8月8日在1:48
#2 楼
密码分析的适用性是什么？
它似乎不直接适用于密码分析，原因有两个：
50 Qbits不足以解决任何加密问题；要将Shor或Grover的算法应用于任何现实问题，您最终将需要成千上万。
看来他们并没有解决退相干问题。也就是说，在量子计算机中，您最终将获得对运行状态的随机扰动。密码计算需要相当长的时间（比我们预期的要长得多，而不会期望发生这样的随机事件），并且对此类扰动非常敏感。他们需要做的是运行纠错逻辑（具有多个物理qbit代表一个逻辑1，并具有检测物理qbit之一上的这种扰动并对其进行校正的逻辑。）
现在，我并不是说IBM试图构建的东西是没有用的。首先，化学建模所需的计算似乎很适合它们。
虽然这对于加密术不是立即有用的，但这是迈向真正量子计算机的又一步（其中“真实”的意思是“实际上可以解决一个有趣的密码问题）。
评论
$ \ begingroup $
我将最后一句话扩展为：实际上可以比同等价位的经典计算机更快地解决一个有趣的密码学问题。
$ \ endgroup $
–卡巴斯德
17 Mar 6 '17 at 23:31
$ \ begingroup $
@kasperd：实际上，如果可以用一台可行的经典计算机完全解决密码问题，那就没意思了...
$ \ endgroup $
–雨披
17 Mar 7 '17 at 0:08
$ \ begingroup $
即使量子计算机没有足够的量子位来一次性解决密码问题，也可以迭代地使用它，从而通过一次可以计算的因素来实质上减少搜索空间吗？
$ \ endgroup $
–纳特
17 Mar 7 '17 at 2:24
$ \ begingroup $
@Nat通常，这是行不通的，就像您一次不能破解哈希或加密（或密码，就像电影中经常显示的那样）一样。对于那些量子算法，您实际上一次需要所有qbits-需要对所有qbits进行完全纠缠。
$ \ endgroup $
– tylo
17 Mar 7 '17 at 10:38
$ \ begingroup $
@tylo只是为了确认一下，为了简单起见，使用少量数字表示，蛮力搜索空间将具有100种可能性，而量子计算机仅具有足够的量子位来破解10种可能性的空间。然后，不可能通过将其分解为十个10空间来尝试强行强制100空间，然后反复尝试每个空间？
$ \ endgroup $
–纳特
17 Mar 8 '17在9:38
#3 楼
我不确定100％是否有针对密码分析的直接用途。但是，如果将该机器应用于一般的机器学习和数据科学等其他学科，则可能会对加密工作产生影响。例如，在数据科学中，神经网络可以成为解决许多问题的有效工具。问题在于它们运行缓慢，并且是在少数情况下可以解决此问题的硬件之一，可以解决的问题之一。现在，谁知道未来会带来什么。评论
$ \ begingroup $
据我所知，神经网络在用于普通加密方案的密码分析（有或没有量子计算机）中没有任何应用。
$ \ endgroup $
–伊夫让尼
19年11月5日在17:51
评论
可能重复的““真正的”量子计算机需要进行密码分析和/或密码攻击吗？”评论不作进一步讨论；此对话已移至聊天。