量子计算百年风云史 “量子比特”何时统治世界？

灵假想（Strong Church-Turing Thesis）进一步推演的话，就是说，如果在物理计算机上计算一个可计算函数的时间是 T 的话，那么在图灵机上的时间则是O（Tc），而这里的常数 c 仅仅由计算机使用的函数类型决定。

　　随着数字计算机的出现，由于机器本身的容量和时间有限，这就使得可计算和不可计算之间的差别在计算机的实际应用上显得越来越重要，皮特·休尔（Peter Williston Shor）这样评价道，"如果所有计算机跑完一个可计算函数的时间里，太阳都燃烧殆尽了，这在实用方面可一点都不好。"

　　于是，一种新的迥异于传统算法的计算机呼之欲出。

　　1970年，斯蒂文·威斯纳（Steven Wiesner）就设想量子信息处理是解决密码逻辑认为较好的一种方式，这是量子计算最早的火花。在10多年后，在爱德华·福莱德金（Edward Fredkin）的可逆计算理念的启发下，费曼为大家开辟了那条新路。

　　费曼相信，一台基于量子力学现象的计算机在模仿量子力学现象上有着近水楼台先得月的先天优势。

　　"自然不是经典的，如果你想模拟自然的话，那你最好去用量子力学。"

　　在1982年发表的一篇论文中，诺贝尔奖得主费曼认为，在计算机上模拟量子力学内在地就需要指数级增长的投入，而他给出的建议则是，使用量子计算机。费曼相信，一台基于量子力学现象的计算机在模仿量子力学现象上有着近水楼台先得月的先天优势——早在1980年，保罗·贝尼奥夫（Paul Benioff）就在论文里提到了基于图灵机制造微量子力学系统计算机模型的可能性。

　　1985年，牛津大学的大卫·道勅（David Deutsch）在一篇论文里给出了量子计算的抽象模型，但是，此时大家的疑问还是，量子计算机究竟能解决哪些实际问题。7年后，道勅和理查德·约饶（Richard Jozsa）在论文里给出了他们的肯定答案：

　　"比起任何基于确定性算法的经典计算机，量子计算机在解决问题上所花的时间要少得多；比起任何基于随机算法的计算机的预期时间，量子计算机也相对更少。"

　　但是仅仅有量子计算机的设想还是远远不够的，没有算法支持的计算机无疑远远都只能停留在遐想阶段，要让所有人都真正信服量子计算机的巨大先进性，他们还需要更具说服力的事实。

　　正是从20世纪90年代开始，量子计算的研究取得了前所未有的丰硕成果，在各大公司实验室和院校机构的共同推动下，量子计算从科学家论文中的设想、算法逐渐落实到到实际制造的机器上。

　　1994年，贝尔实验室的休尔发表了论文，在里面向大家展示了他的量子算法分解大数的质因数的速度如何领先于当时的已知任何计算机——分解一个1000位的数字，传统计算机大约需要耗费10京（《孙子算经》载"万万曰亿，万万亿曰兆，万万兆曰京"）年的时间，而利用量子计算机的话，只需要20分钟左右。

　　休尔的量子算法将会对 RSA 等在内的加密算法和系统造成了显而易见的冲击，在此以前，破解一个 RSA 129位密码需要8个月时间以及1600名计算机用户，然而用量子算法破解 RSA 140位密码也只要数秒的时间而已。

　　休尔的发现使得量子计算机掀起了一场的风暴，不仅席卷了物理学和计算机科学领域，让他们感受到新的计算工具蕴含的巨大潜力，亦使得包括之前一直相信使用 RSA 算法的国家部门和各公司开始认真对待关注这个概念。

　　量子计算机第一次从科学家的象牙塔里走到了世人面前。

　　1995年，舒马赫（Benjamin Schumacher）发表了论文，第一次提出了量子比特信息学上的概念，并创造了"量子比特"（qubit）的说法。

　　比特（bit）是传统计算机中最基础的构件，它只存在两个状态0或1之间，在量子计算机中，情况却并非如此。量子力学告诉我们，量子具有叠加态的特性，因而，量子计算机中的比特——即量子比特——同时就有了0与1的状态，它既可以是1，亦可是0。基于量子平行，我们可以将这两种状态看成是处于两个不同宇宙里，那么，当一个量子比特进行运算时，实际上是处于两个宇宙里的数值在同时执行。

　　包含3个量子比特的寄存器

　　3个比特可以代表8种状态，但是寄存器却只能记录其中的一个结果，而3个量子比特构成的寄存器同时也具备了其线性叠加态效果，于是可以同时记录8种数值结果。通过这样一个简单的例子就能看出来量子计算机惊人的计算能力，是同数目（设为n）比特构成的经典计算机的2n倍。

理论上来说，一个量子比特可以储存的信息是无限的，当被测量时，状态满足一些特定条件的量子比特才会释出0或1那样的结果，也就是说，测量