波士顿哈佛大学附近的CLAY数学研究所，千禧年时曾经发佈一则消息：将提供百万美元的奖金為七个当时未解决的数学问题征求答案。目前为止，12年过去了，只有其中一个“庞加莱猜想”的问题被俄国数学家佩雷尔曼Grigori Perelman于2006年解决。但佩雷尔曼天生淡泊名利，拒绝领奖，也拒绝了同年颁发给他的数学界的诺贝尔奖“菲尔兹”奖，据说此事还在数学界与某数学家演绎出一段幕后故事，不过这是题外话，在此不表。

这七大千禧奖中有一个，是在计算机算法领域颇為著名的 P / NP 問題。

众所周知，计算机的发明为许多必须进行大量数字计算的问题提供了一条捷径。计算机的计算能力是一般的人工计算无法比拟的。一个超级计算机可以以每秒钟进行亿万次运算的速度连续不停地进行运算。一般来说，需要进行数字计算的问题的运算量的大小与表征这个问题大小的变量数目N有关。变量数N越大，解决问题所需的计算时间T也越长。当然，计算时间T也取决于所使用的计算方法。计算机算法就是研究各种计算方法的学问。

所需计算量T与变量数N之间的函数关係因为问题的不同而不同。在有些问题中，T与N成线性关系；而在另一些问题中，则成平方关系；也有可能是随着N的增加而指数增长。

研究算法的科学家们，将需要进行大量计算的问题，按照T随N而增大的函数形式，分為几种不同的类型。第一种叫P型，或称多项式型。计算P型问题所需的时间T与N成多项式级数关系。多项式型问题是计算机可以解决的问题。只要计算机的速度足够快，内存足够大，使用了正确的算法，答案总会即日可待。而另一种NP型的问题，还没有找到任何成功的算法，使得问题的答案能在与N成多项式级数关系增长的时间内解出。但这并不能说明这种算法不存在。所以，这是属于不能确定T与N是否是多项式级数关系的一类问题。此外，还有一类最困难的问题，属于NP-Hard。

在NP型中，有一个数学家们最感兴趣的子集，叫做NP完整型。这个子集中的任何两个问题互相转换所需的时间与N成多项式级数关系。因此，如果找到了一种多项式的算法，解决某个NP完整问题，也就有了多项式的算法，解决所有的NP完整问题，这也就是叫做证明了“NP=P”。反之，如果你能够证明，这种对NP完整型的多项式算法并不存在的话，你就证明了“NP!=P”。CLAY数学研究所的百万大奖，就将颁发给证明了“NP=P”，或者“NP!=P”的人。

看看下面的图，可能更容易理解P / NP 問題：

大多数的数学家们都相信，结论应该是P!=NP，但是要想真正严格地证明这个结论却非常困难，否则怎么会有百万美金的大奖来征求答案呢？不过，2010年8月，曾经有一个惠普实验室的研究员，声称证明了P不等于NP。但他当时只在自己的网站上宣称此事，后来似乎便没有了下文。所以，这应该仍然是一个未解决的问题。

算法问题的实质是计算速度的问题。从理论上来说，现在的这种经典类型的计算机永远处理不了那些计算量按指数增长的问题。这些题目包括著名的“旅行推销员问题”、用于保密通讯的大数的质数分解问题等，还有据说是属于最难的NP-Hard类的围棋必胜问题。不敢说量子计算机都能解决这些困难，但总是提供了一种完全不同于经典图灵机，而是按照量子规律来运行的另一类选择性吧。

遗憾的是，量子理论诞生已有一百年左右的历史，经典计算机使用的芯片制造技术也早已涉及到量子理论，但工作在数亿个经典比特基础上的计算机科学家们，竟晚了大半个世纪，才认识了量子计算。如果早些进行这方面的研究的话，计算机科学也许受益匪浅。回顾计算机发展的历史，从第一台经典计算机问世以来，它在‘尺寸大小’的领域经过了天翻地覆的变化，从一个占据几栋楼房的庞然大物缩小到了人们的手掌上、口袋里。近二十年，计算机技术更是经历了巨大的革命的飞跃，单个芯片上三极管的数目及运算的速度都是以指数形势逐年上升。正是这种高速发展，使经典计算机将很快达到它的极限。那时的三极管的大小将达到原子的尺度。经典计算机，无论是40多年前的充满整栋屋的庞然大物，还是现在的手机型电脑，基本原理却是万变不离其宗，基本构造单元都是比特（bit），不论是用灯泡大小的电子管来实现的一个比特，还是用芯片上的三极管（微米级大小）来表示的比特，都是同样遵循牛顿力学定律。直到费曼观察到用经典计算机模拟量子系统时的 “指数减慢”问题，才促使计算机科学家和物理学家牵手合作，正式启动了研究“量子计算机”的物理实现及算法问题。

也有人将研究“可逆计算” 的IBM科学家R. Landauer誉为量子计算之父。认为他在1961年“可逆计算”领域的发现而导致了量子计算机研究。但实际上，可逆计算的研究只是与量子计算机有关系，并未直接导致量子计算的发展，并且，R. Landauer本人生前（直到1999年去世）都一直不遗余力地批评量子计算机研究。他认为量子计算机“没有考虑各种可能的噪音源，没有考虑实际生产的误差和缺陷，基本没戏。”

当然，虽然费曼早在1982年就预见到量子元件的超强计算功能，但直到1996年，贝尔实验室的W.Shor发展出一种算法之后，有关量子计算机的研究才逐渐成為学术界及一些大型工业研究部门的瞩目课题。计算机学者开始使用和了解奇妙的量子力学规律，物理学家们也将眼光投向计算机科学，关心和探讨适合量子元件运算规律的算法。如果将W.Shor的算法，用在量子计算机上的话，可以在多项式的时间内，将一个大的整数分解為若干质数之乘积。也就是说，如果未来造出了真正实用的量子计算机，在它上面使用W.Shor算法及其它量子算法，前面所说的NP问题，便有可能转换成P型问题。

2001年初，IBM研究中心的科学家们研制出了只有五个比特的量子计算机，并成功地用它进行order finding的计算，為实现W.Shor的算法迈出了第一步。

一个经典计算机的储存量可以用比特的多少来衡量。它运算的快慢可以由每秒鐘能进行的比特的转换数目来决定。量子计算机也是如此，只是构成它的最小信息单元不同于经典的比特，而是前面介绍过的量子比特。

尽管量子计算机的潜力看来似乎很大，实现起来却困难重重。量子比特数目的增加谈何容易！我们现在所使用的手提电脑，硬盘储存量少说也有几十亿个比特，可是，如前面所说，IBM研究中心当时研制出了只有五个比特的量子计算器件，就已引起轰动。

如上几节所述，量子计算器件的潜力的来源是在于量子系统在不与环境互相作用时的不确定性。一旦与环境相互作用，量子器件就会崩塌到一个确定的状态，计算便无法进行下去。困难在于：如何才能将量子计算系统与其环境分开来，使其既能维持它的独立运算能力，而又需要可接近，使人得以控制计算过程，并得到输出结果呢？

要作到以上所述的环境是非常困难的。这也就是為什么，直到近十年来，才有几个实验室，只实现了少数十来个量子比特的计算器件。这些器件有的是基于核磁共振NMR（类似于成象所用的MRI）的实验。实验时，在NMR的机器核心上，撒上一些fluerinated有机液体，然后，通以RF脉冲来激励液体，使其转化成高速处理器，而解决问题的算法便被编码到RF脉冲里。有的是基于3维超导量子比特的计算器件，

下图是IBM的3量子比特的硅片。

(scale: 8mm x 4mm)

照片来自网络，参考IBM的最新报道：

http://www-03.ibm.com/press/us/en/pressrelease/36901.wss

2011年5月，量子计算机领域飞奔出了一匹黑马。加拿大D-Wave公司公布他们造出了第一台128量子比特的“商用量子计算机”- D-Wave-One，还据说卖出了一个单价1000万美金的天价，买主是美国的洛克希勒马丁公司。这个消息一经发布，在业内引起一阵轩然大波。不少量子计算机方面的专家质疑D-Wave-One能否称得上是一台真正意义上的“量子计算机”？

D-Wave声称他们的这个超导绝热的量子计算机，使用了所谓“量子退火算法”，可以比经典算法效率更高地解决离散最优化问题。不过，也只能解决这一种特殊用途的问题。因此，当然不是一台通用意义下的量子计算机。有人认为，顶多是一个费曼所提到过的只能解决某一类问题的仿真机器，至于这个仿真过程有多少量子的成分，人们也不清楚。在他们的博客网页上，对“离散最优化问题”等有一些普及性的描述，有兴趣的读者可去一阅：

http://dwave.wordpress.com/2011/05/11/learning-to-program-the-d-wave-one/

要实现通用的量子计算，满足不同的计算要求，运行各种量子算法，实现输入、输出、和保持量子相干态和纠缠态来进行可靠的运算，是极端困难的。此外，量子计算纠错的问题很难解决。专家们认为，制造出通用、可靠的量子计算机，还有很长的路要走。

即使是进行实验的专家们自己，也很难从他们现在进行的实验，来描述和想象将来量子计算机的形态。因此，科学家们不断把眼光投向新的物理领域，提出种种设想：能否不使用超导？也许用固态NMR？也许用被激光俘获后的冷却离子？也许，量子计算机根本不应该象经典计算机似的用制造芯片的人工技术制造出来，而应该与生物工程、基因研究等结合起来？的确，生物体的生长过程，证明了大自然本身已经完成了人类想人工达到的目的的最困难部分。在生物体内，普通分子便已经会按照量子规律做最复杂的计算，量子计算机已经存在于自然之中，人类又何必多此一举呢。当然，科学家和工程师们总是在不停止地探索物质的奥秘，发展更先进的技术，制造出更新的东西，他们是永远不会放弃的。

上一篇：GHZ定理-續

下一篇：量子隱形傳輸