新算法以外的量子计算机的影响

Question

当大规模量子计算机出现时，基于新原理的算法将对我们加密数据的方式产生影响，Shor的算法使RSA易受攻击，Grover的算法使AES的有效密钥大小减半。

我想知道的是，拥有一台实际的量子计算机将如何影响随后的计算。

使用Grover的算法，AES-256将与今天的AES-128一样安全.但是一台量子计算机也能更快地搜索新的空间吗？因此，我们是否需要双倍大小的键盘作为防御呢？

Answer 1

我没有完全理解你的问题，但我会试试看。据我所知，量子计算机将允许你有效地解决一类问题，即BQP (目前的知识分解是在BQP中)，它比P大，但并不包括所有NP。所以他们不会允许你有效地解决NP问题。

Grovers算法将给出NP-完全问题的sqrt(n)加速比.所以如果你有2^n状态，通过应用Grovers算法，你就可以将它降到2^(n/2)，这是很好的，但仍然是指数的。

Answer 2

还有其他算法已经可以使用了。虽然相对素数分解是非对称密码学中最常用的问题，但是还有许多其他已知的问题(我现在还记不起来)，它们目前还没有一个已知的量子算法来解决。因此，在短期内，如果/当量子计算机存在时，我们仍然有许多被认为是安全的算法。

另一方面，如果它们变得广泛，我们可能能够利用广泛的量子密码学，如量子密钥分配。我理解的基本思想是，你可以使用量子力学原理来保证信息只有一个发射机和一个接收器，这样攻击者实际上就不可能获得有意义的信息访问，因为如果有两个人读取数据，它就会变得一团糟。