复杂性也只不过比指数性的增长稍好，仍未达到多项式的要求

复杂性也只不过比指数性的增长稍好，仍未达到多项式的要求(所谓多项式，指的是当处理数字的位数n增大时，算法所费时间按照多项式的形式，也就是n^k的速度增长)。


非线性
突变，群众革命运动，质变，互相影响，一个方向，

大幅偏离45度基线
波函数就是期望
期望不同，就是不同事物，波函数没有相干性事

原子数目超过一定界限，就是有互相影响了


breakout out of the original trend, reversal, or set up new trend line, tight flag breakout,


第十章 不等式三
http://vip.book.sina.com.cn 2004年05月28日00:00 新浪读书


计算机的发明是20世纪最为重要的事件之一，这个新生事物的出现从根本上改变了人类的社会，使得我们的能力突破极限，达到了一个难以想象的地步。今天，计算机已经渗入了我们生活的每一个角落，离开它我们简直寸步难行。别的不说，各位正在阅读的本史话，便是用本人的膝上型计算机输入与编辑的，虽然拿一台现代的PC仅仅做文字处理简直是杀鸡用牛刀，或者拿伊恩8226;斯图尔特的话说，“就像开着罗尔斯8226;罗伊斯送牛奶”，但感谢时代的进步，这种奢侈品毕竟已经进入了千家万户。而且在如今这个信息商业社会，它的更新换代是如此之快，以致人们每隔两三年就要不断地开始为自己“老旧”电脑的升级而操心，不无心痛地向资本家们掏出那些好不容易积攒下来的银子。


回头看计算机的发展历史，人们往往会慨叹科技的发展一日千里，沧海桑田。通常我们把宾夕法尼亚大学1946年的那台ENIAC看成世界上的第一台电子计算机，不过当然，随着各人对“计算机”这个概念的定义不同，人们也经常提到德国人Konrad Zuse在1941年建造的Z3，伊阿华州立大学在二战时建造的ABC(Atanasoff-Berry Computer)，或者图灵小组为了破解德国密码而建造的Collosus。不管怎么样，这些都是笨重的大家伙，体积可以装满整个房间，有的塞满了难看的电子管，有的拖着长长的电线，输入输出都靠打孔的纸或者磁带，和现代轻便精致的家庭电脑比起来，就好像美女与野兽的区别。但是，如果我们把看起来极为不同的这两位从数学上理想化，美女和野兽在本质上却是一样的！不管是庞大的早期计算机，还是我们现在使用的PC，它们其实都可以简化成这样一种机器：它每次读入一个输入，并且视自己当时内态的不同，按照事先编好的一个规则表做出相应的操作：这操作可以是写入输出，或者是改变内态，或者干脆什么都不做乃至停机。这里的关键是，我们机器的输入和输出可以是无限多的，但它的内态和规则表却必须是有限的。这个模型其实也就是一切“计算机”的原型，由现代计算机的奠基人之一阿兰8226;图灵(Alan Turing)提出，也称作“图灵机”(The Turing Machine)。在图灵的原始论文中，它被描述成某种匣子样的东西，有一根无限长的纸带贯穿其中，一端是作为输入，另一端则是输出。磁带上记录了信息，一般来说是0和1的序列。这台机器按照需要移动磁带，从一端读入数据，并且按照编好的规则表进行操作，最后在另一端输出运算结果。


我们如今所使用的电脑，不管看上去有多精巧复杂，本质上也就是一种图灵机。它读入数据流，按照特定的算法来处理它，并在另一头输出结果。从这个意义上来讲，奔腾4和286的区别只不过是前者更快更有效率而已，但它们同样做为图灵机来说，所能做到的事情其实是一样多的！我的意思是，假如给予286以足够的时间和输出空间(可以记录暂时的储存数据)，奔腾机所能做到的它同样可以做到。286已经太高级了，即使退化成图灵机最原始的形式，也就是只能向左或向右移动磁带并做出相应行动的那台机器，它们所能解决的事情也是同样多的，只不过是快慢和效率的问题罢了。


计算机所处理的信息在最基本的层面上是2进制码，换句话说，是0和1的序列流。对计算机稍稍熟悉的朋友们都知道，我们把每一“位”信息称作一个“比特”(bit，其实是binary digit的缩写)，例如信息1010，就包含了4个bits。8个bits就等于1个byte，1024个bytes就是1K，1024K=1M，1024M＝1G，各位想必都十分清楚了。


对于传统的计算机来说，1个bit是信息的最小单位。它要么是0，要么是1，对应于电路的开或关。假如一台计算机读入了10个bits的信息，那相当于说它读入了一个10位的2进制数(比方说1010101010)，这个数的每一位都是一个确定的0或者1。这在人们看来，似乎是理所当然的。


但是，接下来就让我们进入神奇的量子世界。一个bit是信息流中的最小单位，这看起来正如一个量子！我们回忆一下走过的路上所见到的那些奇怪景象，量子论最叫人困惑的是什么呢？是不确定性。我们无法肯定地指出一个电子究竟在哪里，我们不知道它是通过了左缝还是右缝，我们不知道薛定谔的猫是死了还是活着。根据量子论的基本方程，所有的可能性都是线性叠加在一起的！电子同时通过了左和右两条缝，薛定谔的猫同时活着和死了。只有当实际观测它的时候，上帝才随机地掷一下骰子，告诉我们一个确定的结果，或者他老人家不掷骰子，而是把我们投影到两个不同的宇宙中去。


大家不要忘记，我们的电脑也是由微观的原子组成的，它当然也服从量子定律(事实上所有的机器肯定都是服从量子论的，只不过对于传统的机器来说，它们的工作原理并不主要建立在量子效应上)。假如我们的信息由一个个电子来传输，我们规定，当一个电子是“左旋”的时候，它代表了0，当它是“右旋”的时候，则代表1(通常我们会以“上”和“下”来表示自旋方向，不过可能有读者会对“上旋”感到困惑，我们换个称呼，这无所谓)。现在问题来了，当我们的电子到达时，它是处于量子叠加态的。这岂不是说，它同时代表了0和1？


这就对了，在我们的量子计算机里，一个bit不仅只有0或者1的可能性，它更可以表示一个0和1的叠加！一个“比特”可以同时记录0和1，我们把它称作一个“量子比特”(qubit)。假如我们的量子计算机读入了一个10bits的信息，所得到的就不仅仅是一个10位的二进制数了，事实上，因为每个bit都处在0和1的叠加态，我们的计算机所处理的是2^10个10位数的叠加！


换句话说，同样是读入10bits的信息，传统的计算机只能处理1个10位的二进制数，而如果是量子计算机，则可以同时处理2^10个这样的数！


利用量子演化来进行某种图灵机式的计算早在70年代和80年代初便由Bennett，Benioff等人进行了初步的讨论。到了1982年，那位极富传奇色彩的美国物理学家理查德8226;费因曼(Richard Feynman)注意到，当我们试图使用计算机来模拟某些物理过程，例如量子叠加的时候，计算量会随着模拟对象的增加而指数式地增长，以致使得传统的模拟很快变得不可能。费因曼并未因此感到气馁，相反，他敏锐地想到，也许我们的计算机可以使用实际的量子过程来模拟物理现象！如果说模拟一个“叠加”需要很大的计算量的话，为什么不用叠加本身去模拟它呢？每一个叠加都是一个不同的计算，当所有这些计算都最终完成之后，我们再对它进行某种幺正运算，把一个最终我们需要的答案投影到输出中去。费因曼猜想，这在理论上是可行的，而他的确猜对了！


1985年，我们那位在埃弗莱特的谆谆教导和多宇宙论的熏陶下成长起来的大卫8226;德义奇闪亮登场了。他仿照图灵当年走的老路子，成功地证明了，一台普适的量子计算机是可能的。所谓“普适机”(universal machine)的概念可能对大家有点陌生以及令人困惑，它可以回到图灵那里，其基本思想是，存在某种图灵机，把一段指令编成合适的编码对其输入，可以令这台机器模拟任何图灵机的行为。我无意在这里过于深入细节，因为那是相当费脑筋的事情，虽然其中的数学一点也不复杂。如果各位有兴趣深入探索的话可以参阅一些介绍图灵工作的文章(我个人还是比较推荐彭罗斯的《皇帝新脑》)，在这里各位所需要了解的无非是：我们聪明睿智的德义奇先生证明了一件事，那就是我们理论上可以建造一种机器，它可以模拟任何特殊量子计算机的过程，从而使得一切形式的量子计算成为可能。传统的电脑处理信息流的时候用到的是所谓的“布尔逻辑门”(Boolean Logic Gate)，比如AND，OR，NOT，XOR等等。在量子计算机中只需把它们换成相应的量子逻辑门即可。


说了那么多，一台量子计算机有什么好处呢？


德义奇证明，量子计算机无法实现超越算法的任务，也就是说，它无法比普通的图灵机做得更多。从某种确定的意义上来说，量子计算机也是一种图灵机。但和传统的机器不同，它的内态是不确定的，它同时可以执行多个指向下一阶段的操作。如果把传统的计算机称为决定性的图灵机(Deterministic Turing Machine, DTM)，量子计算机则是非决定性的图灵机(NDTM)。德义奇同时证明，它将具有比传统的计算机大得多的效率。用术语来讲，执行同一任务时它所要求的复杂性(complexity)要低得多。理由是显而易见的，量子计算机执行的是一种并行计算，正如我们前面举的例子，当一个10bits的信息被处理时，量子计算机实际上操作了2^10个态！


在如今这个信息时代，网上交易和电子商务的浪潮正席卷全球，从政府至平民百姓，都越来越依赖于电脑和网络系统。与此同时，电子安全的问题也显得越来越严峻，谁都不想黑客们大摇大摆地破解你的密码，侵入你的系统篡改你的资料，然后把你银行里的存款提得精光，这就需要我们对私隐资料执行严格的加密保护。目前流行的加密算法不少，很多都是依赖于这样一个靠山，也即所谓的“大数不可分解性”。大家中学里都苦练过因式分解，也做过质因数分解的练习，比如把15这个数字分解成它的质因数的乘积，我们就会得到15=5×3这样一个唯一的答案。


问题是，分解15看起来很简单，但如果要分解一个很大很大的数，我们所遭遇到的困难就变得几乎不可克服了。比如，把10949769651859分解成它的质因数的乘积，我们该怎么做呢？糟糕的是，在解决这种问题上，我们还没有发现一种有效的算法。一种笨办法就是用所有已知的质数去一个一个地试，最后我们会发现10949769651859＝4220851×2594209(数字取自德义奇的著作The Fabric of Reality)，但这是异常低效的。更遗憾的是，随着数字的加大，这种方法所费的时间呈现出几何式的增长！每当它增加一位数，我们就要多费3倍多的时间来分解它，很快我们就会发现，就算计算时间超过宇宙的年龄，我们也无法完成这个任务。当然我们可以改进我们的算法，但目前所知最好的算法(我想应该是GNFS)所需的复杂性也只不过比指数性的增长稍好，仍未达到多项式的要求(所谓多项式，指的是当处理数字的位数n增大时，算法所费时间按照多项式的形式，也就是n^k的速度增长)。


所以，如果我们用一个大数来保护我们的秘密，只有当这个大数被成功分解时才会泄密，我们应当是可以感觉非常安全的。因为从上面的分析可以看出，想使用“暴力”方法，也就是穷举法来破解这样的密码几乎是不可能的。虽然我们的处理器速度每隔18个月就翻倍，但也远远追不上安全性的增长：只要给我们的大数增加一两位数，就可以保好几十年的平安。目前最流行的一些加密术，比如公钥的RSA算法正是建筑在这个基础之上。


但量子计算机实现的可能使得所有的这些算法在瞬间人人自危。量子计算机的并行机制使得它可以同时处理多个计算，这使得大数不再成为障碍！1994年，贝尔实验室的彼得8226;肖(Peter Shor)创造了一种利用量子计算机的算法，可以有效地分解大数(复杂性符合多项式！)。比如我们要分解一个250位的数字，如果用传统计算机的话，就算我们利用最有效的算法，把全世界所有的计算机都联网到一起联合工作，也要花上几百万年的漫长时间。但如果用量子计算机的话，只需几分钟！一台量子计算机在分解250位数的时候，同时处理了10^500个不同的计算！


更糟的事情接踵而来。在肖发明了他的算法之后，1996年贝尔实验室的另一位科学家洛弗8226;格鲁弗(Lov Grover)很快发现了另一种算法，可以有效地搜索未排序的数据库。如果我们想从一个有n个记录但未排序的数据库中找出一个特定的记录的话，大概只好靠随机地碰运气，平均试n/2次才会得到结果，但如果用格鲁弗的算法，复杂性则下降到根号n次。这使得另一种著名的非公钥系统加密算法，DES面临崩溃。现在几乎所有的人都开始关注量子计算，更多的量子算法肯定会接连不断地被创造出来，如果真的能够造出量子计算机，那么对于现在所有的加密算法，不管是RSA，DES，或者别的什么椭圆曲线，都可以看成是末日的来临。最可怕的是，因为量子并行运算内在的机制，即使我们不断增加密码的位数，也只不过给破解者增加很小的代价罢了，这些加密术实际上都破产了！


2001年，IBM的一个小组演示了肖的算法，他们利用7个量子比特把15分解成了3和5的乘积。当然，这只是非常初步的进展，我们还不知道，是否真的可以造出有实际价值的量子计算机，量子态的纠缠非常容易退相干，这使得我们面临着技术上的严重困难。虽然2002年，斯坦弗和日本的科学家声称，一台硅量子计算机是可以利用现在的技术实现的，2003年，马里兰大学的科学家们成功地实现了相距毫米的两个量子比特的互相纠缠，一切都在向好的方向发展，但也许量子计算机真正的运用还要过好几十年才会实现。这个项目是目前最为热门的话题之一，让我们且拭目以待。


就算强大的量子计算机真的问世了，电子安全的前景也并非一片黯淡，俗话说得好，上帝在这里关上了门，但又在别处开了一扇窗。量子论不但给我们提供了威力无比的计算破解能力，也让我们看到了另一种可能性：一种永无可能破解的加密方法。这是另一个炙手可热的话题：量子加密术(quantum cryptography)。如果篇幅允许，我们在史话的最后会简单描述一下这方面的情况。这种加密术之所以能够实现，是因为神奇的量子可以突破爱因斯坦的上帝所安排下的束缚——那个宿命般神秘的不等式。而这，也就是我们马上要去讨论的内容。


但是，在本节的最后，我们还是回到多宇宙解释上来。我们如何去解释量子计算机那神奇的计算能力呢？德义奇声称，唯一的可能是它利用了多个宇宙，把计算放在多个平行宇宙中同时进行，最后汇总那个结果。拿肖的算法来说，我们已经提到，当它分解一个250位数的时候，同时进行着10^500个计算。德义奇愤愤不平地请求那些不相信MWI的人解释这个事实：如果不是把计算同时放到10^500个宇宙中进行的话，它哪来的资源可以进行如此惊人的运算？他特别指出，整个宇宙也只不过包含大约10^80个粒子而已。但是，虽然把计算放在多个平行宇宙中进行是一种可能的说法(虽然听上去仍然古怪)，其实MWI并不是唯一的解释。基本上，量子计算机所依赖的只是量子论的基本方程，而不是某个解释。它的模型是从数学上建筑起来的，和你如何去解释它无干。你可以把它想象成10^500个宇宙中的每一台计算机在进行着计算，但也完全可以按照哥本哈根解释，想象成未观测(输出结果)前，在这个宇宙中存在着10^500台叠加的计算机在同时干活！至于这是如何实现的，我们是没有权利去讨论的，正如我们不知道电子如何同时穿过了双缝，猫如何同时又死又活一样。这听起来不可思议，但在许多人看来，比起瞬间突然分裂出了10^500个宇宙，其古怪程度也半斤八两。正如柯文尼在《时间之箭》中说的那样，即使这样一种计算机造出来，也未必能证明多世界一定就比其它解释优越。关键是，我们还没有得到实实在在可以去判断的证据，也许我们还是应该去看看还有没有别的道路，它们都通向哪些更为奇特的方向。