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

蓬勃、最具生命力的光彩。

　　在量子力学争论如火如荼的同时，战火也蔓延世界，战争在摧毁世界旧秩序的同时，也极大地推动了科学技术的发展，而量子计算的最初萌芽就发生在二战里。

　　前奏

　　19世纪的英帝国国力昌隆，在科学领域，英国同样也群星璀璨，在麦克斯韦震古烁今的电磁理论酝酿诞生的同时，查尔斯·巴贝奇（Charles Babbage）也在不断失败的处境中尝试着完成差分机和分析机，尽管至死都没有完成设备的组装和完整运行，但是，这些能够通过逻辑化的运作进行复杂数学运算的设备雏形却使得人们认识到通用计算机的可能性。

　　1936年，阿兰·图灵提出了现代计算机的概念。 （来源：NPL/Science Museum）

　　1936年，阿兰·图灵（Alan Turing）在论文《论数字计算在决断难题中的应用》（On Computable Numbers， with an Application to the Entscheidungsproblem）里提出了现代计算机的概念，天才的图灵是如此描述这样的设备的："发明一台用来计算所有可计算数列的设备是完全可能的。"

　　1944年，世界上第一台电子数字可编程计算机巨人（Colossus）在英国问世，它的用途就是为了破解德军通信密码，在冷战期间，为了掩盖英国有能力破解洛伦兹密码机（Lorenz Cipher）的事实，丘吉尔下令销毁绝大部分巨人计算机。1946年，ENIAC在美国曝光，在战时，这台设备设计之初的主要目的就是来计算火炮射表，而它最早承担的项目还包括计算热核武器的可行性。

　　随着战争结束以及社会各行各业的复兴需求，体积庞大但在运算上有着惊人优势的计算机从战争期间的隐蔽战线开始越来越多地出现在民用和商业领域。

　　1951年，费朗替（Ferranti）公司为曼彻斯特大学开发出了世界上第一台商用计算机Ferranti Mark 1，同年，美国人口调查局采购了UNIVAC I，这是世界上第一台被大规模制造的计算机，仅仅3年之后，IBM 推出了"相对"而言更小更便宜的计算机IBM 650 ，这台设备净重超过900千克，算上电力供应装置之后则在1.35吨以上，售价高达50万美元或者每月租金为3500美元。

　　1947年，双体性晶体管问世，并逐渐取代真空管在以往计算机设计中的位置，1953年，世界上第一台可运行的晶体管计算机在英国问世，两年后，另一台包含200个晶体管、1300个固态二极管的晶体管计算机问世。相比真空管，晶体管的体积更小、耗能更少、更稳定而且寿命更长，但是最重要的是，它能容纳数以万计的逻辑电路。在1952年，集成电路概念首次被杰弗里·达莫（Geoffrey W.A. Dummer）提出，6年后，世界上第一个可运行的集成电路问世。晶体管和集成电路的出现意味着计算机有了更快的运行速度和更强大的计算能力。

　　1965年，英特尔联合创始人戈登·摩尔（Gordon Moore）在文章中提出了被后人补充进而成型的摩尔定律，10年后，摩尔本人再次对此定律做出调整："在这10年末期，倾斜程度（半导体芯片上集成的晶体管和电阻数量）将每2年增加大约1倍。"

　　计算机的发展轨迹按照摩尔的预言波澜不惊地前行着，大众继续享受着计算机小型化、廉价化和性能提升带来的种种便利优势。但是，科学界却异常焦急，大量新的议题和项目迫切需要计算能力更加强大的计算机设备帮助，Altas、CDC6600、Cray 两代以及90年代面世的富士"数值风洞"（Numerical Wind Tunnel）、Hitachi SR2201等超级计算机尽管已经在一定程度上解决了科学家的需求，但是，他们对当时计算机的能力依然感到不满足而迫切地需要一种新的更加强大、速度更快的计算机设备。

　　匣中的失乐

　　数学上，算法是对函数进行有效计算的方法，算法研究的一个重要的切入点是寻找可以有效计算的函数，这类函数叫做递归函数。

　　1931年，哥德尔（Kurt Friedrich Gödel）提出并证明了后来被统称为哥德尔不完备定理的两条定理，而根据哥德尔不完备定理，一些函数在数学上是不能被算法计算的。

　　哥德尔对"计算"（computation）做出了清晰的定义，尽管在论文里这些定义看上去不尽相同，但它们最后都归于同一类可计算函数里。而邱奇-图灵假想（Church-Turning thesis）做出这样的判断，任何在算法上可计算的函数都能被图灵机计算。

　　计算机科学家把一个运行时间随着输入大小而像多项式展开那样增长的算法叫做"多项式时间"（polynomial-time），如果一个问题用多项式时间就能解决的话，大家就把它称作复杂类度为P的问题——绝大多数P类问题都用有效的算法解决，然而，大多数不属于P类的问题无论花多少时间也解决不了。

按照强邱奇－图