shor 的指数优势是相对于"已知最好的经典算法"，没有被证

shor 的指数优势是相对于"已知最好的经典算法"，没有被证明。 没有人证明过大数分解对经典计算机一定难。分解不是 NP 完全问题，理论上完全可能存在一个多项式时间的经典分解算法，只是五十年来没人找到。如果哪天找到了，Shor 的优势就没了。这一点和"反量子化"不同：反量子化是借走量子算法的思路，而这里需要的是一个与 QFT 完全无关的全新经典算法