algorithm - 量子算法可以用于加密吗？

Question

量子算法有用吗？

有没有人成功地将量子算法用于任何用途？

Answer 1

“量子算法”是在量子计算机上运行的算法。

有些事情可以在量子计算模型中快速完成，但不知道(或相信)经典计算是可能的:Discrete logarithm和 Integer factorisation (参见 Shor's algorithm )在 BQP 中, 但不认为在 P (或 BPP )中。因此，当/如果构建了一台量子计算机，众所周知它可以破解 RSA 和大多数当前的密码学。

但是，

• 量子计算机不能(不相信，我的意思是)在多项式时间内解决 NP 完全问题，更重要的是，
• 还没有人 build 过量子计算机，甚至不清楚是否有可能 build 一台——避免退相干等。(有人声称量子计算机的量子位数量有限——5到 10，但显然它们没有多大用处。)

"Well, there's a quantum computer that can factor 15, so those of you using4-bit RSA should worry." -- Bruce Schneier

[还有量子密码学的概念，它是基于量子信道的密码学，与量子计算完全不同。]