[转] 走近量子纠缠（17）——量子计算机

17.量子计算机
波士顿哈佛大学附近的CLAY数学研究所，千禧年时曾经发布一则消息：将提供百万美元的奖金为七个当时未解决的数学问题征求答案。目前为止（2012年），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 问题：