周末胡乱科普量子计算机——经典计算机与NP问题

Mr.X

呵呵，其实俺也不懂，不过先胡说几句，希望专家们批判。

量子计算机么，当然与量子力学有关啦。不过呢，温故而知新，俺还是先说说现
在的计算机，为了与“量子计算机”区别，姑且称为“经典计算机”。

计算机么，大家都知道，不外乎存储、计算、输入输出之类。存储的基本单位是
“位”，英文词叫bit。现在好象都改用音译，叫啥子“比特”，有点崇洋媚
外，俺觉得不大好，所以本文都叫“位”。
每一个“位”，可以存储一个二进制数。为了与“量子计算机”接轨，不妨把
“位”所储存的数称为“位”的“状态”，而把对“状态”的读取称为“测
量”。

经典计算机，就是大家现在手头用的这种。它的特点，简单地讲，有以下两点：

（1）每个“位”的状态在任何时候都是完全确定的，要么是“0”，要么是
“1”，与我们是否去“测量”无关。

（2）计算机对于“位”的操作也是完全决定性的，而且每次操作只改变所操作
的位的“状态”。计算机进行的一切操作，最终都被分解成为对“位”的操作。

简单地说，经典计算机的任何操作，都可以分解成一下两类基本操作：

（1）对单个“位”的操作，比如取反；

（2）对两个“位”的操作，比如乘法、加法。

因此，我们只要能制造出实现这两类操作的元件，原则上就可以建造一台经典计
算机了。这一点看来是很直观的，但却是非常重要的。如果这一点不成立，那
么，就必须分别制造对单个、两个、三个直至无穷个“位”进行操作的元件，于
是建造计算机就必须建造无穷多种不同的元件，这就使得建造计算机成为不可能
的事情了。很幸运的是，这不是事实。

经典计算机能做的事情，相信大家都很清楚的。那么，有没有经典计算机不能做
的事情呢？从理论上讲，可以认为是没有的。只要有足够的存储空间、足够的时
间，任何问题都能解决。（当然了，我们这里已经假定，解决问题的方案是已知
的。）但是呢，这二者从来都不是无限的，我们必须面对现实。那么，现实地
说，什么样的问题是可以解决的呢？

作为一个例子，让我们考虑这样一个问题：输入一个合数，它是由两个质数相乘
得到的，现在要求把这两个质数找出来。如果输入的数需要用N个“位”来存
储，而完成这个计算需要进行的基本操作次数记为F(N)。那么，如果F(N)是N的
一个多项式，这个问题就被称为“P问题”也就是“多项式(Polynomial)问
题”；如果F(N)随着N的增长速度超过了N的所有多项式，比方说，F(N)是N的指
数函数，那么，这个问题就被称为“NP问题”也就是“非多项式
(Non-Polynomial)问题”。

如果一个问题对于经典计算机而言是P问题，那么是可以解决的，如果是NP问
题，就无能为力了。

对于经典计算机，NP问题数不胜数，而且不少都是很有用处的事情。有些问题本
身是P问题，但其逆向问题却是NP问题。一个著名的例子就是把输入的两个质数
相乘，对于经典计算机，这是一个P问题。它的逆问题是：输入一个合数，它是
两个质数相乘得到的，现在要找到这两个质数。这个问题，对于经典计算机而
言，是一个NP问题。

这个事实非常有用，它成为现代密码学的理论基石。比如，某个机构要秘密地收
集一些数据。为了建立密码，寻找两个很大的质数，用它们来得到一个用于解密
的密码，然后把他们相乘，用得到的合数来得到用于加密的密码。现在，把那个
合数和加密方法公布出去，这样，人们可以把数据加密之后发送到这个机构，然
后这个机构来解密。由于从这个合数得到那两个质数对于经典计算机是NP问题，
只要数足够大，密码就不可能被破解。

大家注意，上面一直强调“对于经典计算机而言”。

那么，是否有可能，同一个问题，对于经典计算机是NP问题，对于“量子计算
机”就是P问题呢？的确如此，上面那个例子正好就是这样的。具体如何，下回
再说。 


【虹桥科教论坛网友文库(www.rainbowplan.org/cgi-bin/edu/mainpage.pl)】