random - 量子计算机对伪随机发生器的可预测性

Question

未来经典的伪随机发生器是否可以被强大的量子计算机预测，或者是否证明这是不可能的？

如果它们是可预测的，科学家是否知道是否存在量子计算机无法预测的 PRG？

Answer 1

经典密码伪随机数生成器 (CPRNG) 的安全性始终基于一些困难假设，例如“分解很困难”或“与 SHA-256 函数冲突很难”。

量子计算机使一些计算问题变得更容易。这违反了一些旧的硬度假设。但不是全部。

例如，blum blum shub很可能被量子计算机破解，但没有人知道如何用量子计算机破解基于格的密码学。证明你可以用量子计算机破解所有经典的 CPRNG，就等于证明了BQP = NP，预计情况并非如此。

即使量子计算机确实打破了所有经典的 CPRNG，它们也恰好填补了这个漏洞。它们可以创建“爱因斯坦认证”的随机数。