量子模拟器构成什么威胁？

Question

我最近在phys org上看到一篇文章，在一台传统的计算机上做了某种“量子模拟”来计算素数概率，这篇文章(以及相关的论文)也提到了shor。

这个模型对当前的密码学构成了什么威胁？

https://phys.org/news/2018-04-quantum-simulator-faster-route-prime.html

https://arxiv.org/abs/1704.03174

Answer 1

这个模型对当前的密码学构成了什么威胁？

你的意思是“他们的算法在量子模拟器上运行对密码学构成什么样的威胁”？

如果是的话，答案是“没有”。是的，有量子模拟器(在经典计算机上运行)，可以运行量子算法。然而，模拟$n$纠缠态需要$O(2^n)$内存和时间，所以在真实的量子计算机上运行的量子算法会使仿真器花费指数时间，我们已经可以比经典计算机上的计算速度更快。

这些模拟器对于研究一台真正的(即可靠的)量子计算机一旦建成就能做什么很有用；它们在实际解决问题方面并不特别有用。

另一方面，如果问题是“他们有了一种新的因子分解的量子算法；一旦我们有了一台真正的量子计算机，这会带来什么威胁？”

对此的回答是“目前所知的不多”。我们已经有了Shor算法，它可以考虑多项式的时间。它们的算法可能运行得更快(或者使用更少的量子位或其他资源)，因此更实用。然而，对于Shor的算法，任何依赖于因式分解困难的东西都被假定已经被破坏了--这个算法(至多)会使它更坏一些。

另外，在常用的公钥密码体制中，只有RSA和Pallier依赖于因式分解的困难。Shor的算法还解决了离散日志问题(也包括DH和ECC)；他们没有提到他们的新算法是否可以用来解决这些问题。