量子计算机目前的进展是什么，如果量子计算机出现了，我们是否不再需要平时的优化了？

量子计算机因为采用了量子比特而带来独特的优势 ^[1] ，但是量子计算的应用价值，坦白说直到目前为止都没有特别明晰。与这一现状对应的是，量子计算在舆论宣传中被过度渲染成无所不能，而且速度快亿倍以上等等，这显然是媒体人为了文章点击率的耸人听闻式过度发挥，并不是真实情况。

抛开量子比特的基本性质和实现这方面的复杂细节不谈，量子计算的潜力完全在于量子计算算法(Quantum algorithms) ^[2] . 这一特性不同于我们对普通通用计算机的理解。在通用计算机上，已经有基础的加减乘除等基础运算，基于这些基础运算设计一些常见的如「卷积」、「微分」、「积分」以及更高层次的「斐波那契数列」、「回归」、「分类」等算法是比较自然而然的。但是在量子计算范畴下，这种自然而然的逻辑是不存在的，这跟量子力学奇特的性质有关。

这也就造成了量子计算不同于普通计算机通用计算的发展能力。在量子计算中，一样需要设计每一步的步骤(比如某个数的因子分解）的基础算法，然后基于这些基础算法建设更复杂的计算应用。在类似于因子分解这样的算法上，量子计算拥有更好的时间复杂度 ^[3] . 但是在普通的加减乘除运算上，量子计算的时间复杂度更差，计算开销显著更差 ^{[4] [5]} . 所以，量子计算机不可能完全取代普通通用计算的计算机。要发挥量子计算的优势，关键在于设计量子计算算法。这类算法只是用于专用计算，也就是应用场景非常特定的计算。这也就决定了，发挥量子计算优势的量子计算算法设计是困难的，成本高的 ^[2] . 而通用计算机理论上天然可以进行任意这类计算，只是在时间复杂度上有可能不可接受。

目前为止，在搜集量子计算算法的Quantum Algorithm Zoo网站中，一共有430种专用算法。而第一种量子计算算法 秀尔算法(Shor's algorithm) 的出现，已经过去了27年 ^[6] . 这种发展速度，对应理论上无限种的算法数量来说，并不能让人对量子计算的发展前景感到太乐观。

第一种量子计算算法秀尔算法，把分解整数质因素的指数时间复杂度 \mathcal{O}\left( e^{1.9\left( log\: N \right)^{1/3}\left( log \: log \: N \right)^{2/3}} \right) 下降到多项式时间 \mathcal{O}\left( \left( log\:N \right)^2 \left( log\: log\: N \right)\left( log\:log\:log\:N \right) \right) . 这意味着，依赖大数因数分解困难性的RSA加密算法 ^[7] ，在量子计算下变得不再安全了。因为这一问题，后量子密码学(Post-quantum cryptography) ^[8] 出现，它依赖不可能被量子计算有效解决的算法来对抗量子计算的优势能力。目前应用广泛的包括格密码(Lattice-based Cryptography) ^[9] 等等。后量子密码学的发展和应用，本身也说明了量子计算的局限性，它的优势能力是可以被规避的。

从目前的情况来看，量子计算肯定不会取代我们日常使用的通用计算机，它更像是一个辅助工具，而且应用场景极为有限，应用场景的发展潜力也比较有限。目前广泛的炒作宣传已经透资了其潜在的价值，作为普通民众还是应当保持冷静，不要跟风炒作，被人在资本市场割韭菜。

参考

1. ^ Holevo, A. S. (1973). Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9(3), 3-11.
2. ^ ^{a b} Montanaro, A. (2016). Quantum algorithms: an overview. npj Quantum Information, 2(1), 1-8.
3. ^ Abbott, D. (2003). Dreams versus reality: plenary debate session on quantum computing. arXiv preprint quant-ph/0310130.
4. ^ Draper, T. G. (2000). Addition on a quantum computer. arXiv preprint quant-ph/0008033.
5. ^ Gidney, C. (2018). Halving the cost of quantum addition. Quantum, 2, 74.
6. ^ Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2), 303-332.
7. ^ Cocks, C. C. (1973). A note on non-secret encryption. CESG Memo.
8. ^ Bernstein, D. J., & Lange, T. (2017). Post-quantum cryptography. Nature, 549(7671), 188-194.
9. ^ Micciancio, D., & Regev, O. (2009). Lattice-based cryptography. In Post-quantum cryptography (pp. 147-191). Springer, Berlin, Heidelberg.