浅谈量子计算机的原理

不过，量子计算机这个想法直到1994年PeterShor的出现才使得人们认真起来。大家都知道非对称密码学RSA体系利用的是将两个大素数的乘积因数分解非常困难。一般认为复杂度是O(NlogN)的量级，也就是说一个400位的数要因数分解，最快的超级计算机需要算上百万年的时间。而Shor 发现量子计算机可以用一年的时间就算出来了——量子计算机把RSA破解的复杂度降到O(log2(N))的水平。

另外在1996年，Lov Grover发现量子计算机可以把最短路径的问题从O(N)的复杂度降为O(N-1/2)的水平。

另外，Kadowaki和Nishimori在1998年发现量子退火原理可以加速机器学习的过程。Dwave就是利用这个原理另辟蹊径做出的专门帮助机器学习的量子退火机。

Shor的发现令人兴奋而恐惧——因为如今金融系统等保险等级最高的地方都是使用RSA系统加密的。而一旦实用型的量子计算机出现，这些RSA的公密钥都将作废。甚至人们发现，只要做出一个45个量子比特的量子计算机就可以彻底废除RSA系统。

不过，量子计算机理论上可行，但是实验上非常困难，因为多粒子纠缠实现起来非常困难。所以，十多年前就有人做出5个量子比特的量子计算机。而今天人们的进展也只是10个量子比特。做出更多的量子比特就需要将更多的粒子纠缠起来，以今天的发展速度，要做到45个量子比特需要大概30到50年的时间。

而且，这世上的事情从来都是一物降一物的。就算是高性能的量子计算机做出来了，也会有量子通讯来进行加密。所以，大家不用杞人忧天。