按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
（qubit）。假如我们的量子计算机读入了一个10bits的信息，所得到的就不仅仅是一个10
位的二进制数了，事实上，因为每个bit都处在0和1的叠加态，我们的计算机所处理的是
2^10个10位数的叠加！
换句话说，同样是读入10bits的信息，传统的计算机只能处理1个10位的二进制数，
而如果是量子计算机，则可以同时处理2^10个这样的数！
利用量子演化来进行某种图灵机式的计算早在70年代和80年代初便由Bennett，
Benioff等人进行了初步的讨论。到了1982年，那位极富传奇色彩的美国物理学家理查德？
费因曼（Richard Feynman）注意到，当我们试图使用计算机来模拟某些物理过程，例如量
子叠加的时候，计算量会随着模拟对象的增加而指数式地增长，以致使得传统的模拟很快
变得不可能。费因曼并未因此感到气馁，相反，他敏锐地想到，也许我们的计算机可以使
用实际的量子过程来模拟物理现象！如果说模拟一个“叠加”需要很大的计算量的话，为
什么不用叠加本身去模拟它呢？每一个叠加都是一个不同的计算，当所有这些计算都最终
完成之后，我们再对它进行某种幺正运算，把一个最终我们需要的答案投影到输出中去。
费因曼猜想，这在理论上是可行的，而他的确猜对了！
1985年，我们那位在埃弗莱特的谆谆教导和多宇宙论的熏陶下成长起来的大卫？德义
奇闪亮登场了。他仿照图灵当年走的老路子，成功地证明了，一台普适的量子计算机是可
能的。所谓“普适机”（universal machine）的概念可能对大家有点陌生以及令人困惑，
它可以回到图灵那里，其基本思想是，存在某种图灵机，把一段指令编成合适的编码对其
输入，可以令这台机器模拟任何图灵机的行为。我无意在这里过于深入细节，因为那是相
当费脑筋的事情，虽然其中的数学一点也不复杂。如果各位有兴趣深入探索的话可以参阅
一些介绍图灵工作的文章（我个人还是比较推荐彭罗斯的《皇帝新脑》），在这里各位所需
要了解的无非是：我们聪明睿智的德义奇先生证明了一件事，那就是我们理论上可以建造
一种机器，它可以模拟任何特殊量子计算机的过程，从而使得一切形式的量子计算成为可
能。传统的电脑处理信息流的时候用到的是所谓的“布尔逻辑门”（Boolean Logic Gate）
，比如AND，OR，NOT，XOR等等。在量子计算机中只需把它们换成相应的量子逻辑门即可
。
说了那么多，一台量子计算机有什么好处呢？
德义奇证明，量子计算机无法实现超越算法的任务，也就是说，它无法比普通的图灵
机做得更多。从某种确定的意义上来说，量子计算机也是一种图灵机。但和传统的机器不
同，它的内态是不确定的，它同时可以执行多个指向下一阶段的操作。如果把传统的计算
机称为决定性的图灵机（Deterministic Turing Machine； DTM），量子计算机则是非决定
性的图灵机（NDTM）。德义奇同时证明，它将具有比传统的计算机大得多的效率。用术语来
讲，执行同一任务时它所要求的复杂性（plexity）要低得多。理由是显而易见的，量子
计算机执行的是一种并行计算，正如我们前面举的例子，当一个10bits的信息被处理时，
量子计算机实际上操作了2^10个态！
在如今这个信息时代，网上交易和电子商务的浪潮正席卷全球，从政府至平民百姓，
都越来越依赖于电脑和网络系统。与此同时，电子安全的问题也显得越来越严峻，谁都不
想黑客们大摇大摆地破解你的密码，侵入你的系统篡改你的资料，然后把你银行里的存款
提得精光，这就需要我们对私隐资料执行严格的加密保护。目前流行的加密算法不少，很
多都是依赖于这样一个靠山，也即所谓的“大数不可分解性”。大家中学里都苦练过因式
分解，也做过质因数分解的练习，比如把15这个数字分解成它的质因数的乘积，我们就会
得到15=5×3这样一个唯一的答案。
问题是，分解15看起来很简单，但如果要分解一个很大很大的数，我们所遭遇到的困
难就变得几乎不可克服了。比如，把10949769651859分解成它的质因数的乘积，我们该怎
么做呢？糟糕的是，在解决这种问题上，我们还没有发现一种有效的算法。一种笨办法就
是用所有已知的质数去一个一个地试，最后我们会发现10949769651859＝4220851×
2594209（数字取自德义奇的著作The Fabric of Reality），但这是异常低效的。更遗憾的
是，随着数字的加大，这种方法所费的时间呈现出几何式的增长！每当它增加一位数，我
们就要多费3倍多的时间来分解它，很快我们就会发现，就算计算时间超过宇宙的年龄，
我们也无法完成这个任务。当然我们可以改进我们的算法，但目前所知最好的算法（我想
应该是GNFS）所需的复杂性也只不过比指数性的增长稍好，仍未达到多项式的要求（所谓多
项式，指的是当处理数字的位数n增大时，算法所费时间按照多项式的形式，也就是n^k的
速度增长）。
所以，如果我们用一个大数来保护我们的秘密，只有当这个大数被成功分解时才会泄
密，我们应当是可以感觉非常安全的。因为从上面的分析可以看出，想使用“暴力”方法
，也就是穷举法来破解这样的密码几乎是不可能的。虽然我们的处理器速度每隔18个月就
翻倍，但也远远追不上安全性的增长：只要给我们的大数增加一两位数，就可以保好几十
年的平安。目前最流行的一些加密术，比如公钥的RSA算法正是建筑在这个基础之上。
但量子计算机实现的可能使得所有的这些算法在瞬间人人自危。量子计算机的并行机
制使得它可以同时处理多个计算，这使得大数不再成为障碍！1994年，贝尔实验室的彼得
？肖（Peter Shor）创造了一种利用量子计算机的算法，可以有效地分解大数（复杂性符合多
项式！）。比如我们要分解一个250位的数字，如果用传统计算机的话，就算我们利用最有
效的算法，把全世界所有的计算机都联网到一起联合工作，也要花上几百万年的漫长时间
。但如果用量子计算机的话，只需几分钟！一台量子计算机在分解250位数的时候，同时
处理了10^500个不同的计算！
更糟的事情接踵而来。在肖发明了他的算法之后，1996年贝尔实验室的另一位科学家
洛弗？格鲁弗（Lov Grover）很快发现了另一种算法，可以有效地搜索未排序的数据库。如
果我们想从一个有n个记录但未排序的数据库中找出一个特定的记录的话，大概只好靠随
机地碰运气，平均试n/2次才会得到结果，但如果用格鲁弗的算法，复杂性则下降到根号n
次。这使得另一种著名的非公钥系统加密算法，DES面临崩溃。现在几乎所有的人都开始
关注量子计算，更多的量子算法肯定会接连不断地被创造出来，如果真的能够造出量子计
算机，那么对于现在所有的加密算法，不管是RSA，DES，或者别的什么椭圆曲线，都可以
看成是末日的来临。最可怕的是，因为量子并行运算内在的机制，即使我们不断增加密码
的位数，也只不过给破解者增加很小的代价罢了，这些加密术实际上都破产了！
2001年，IBM的一个小组演示了肖的算法，他们利用7个量子比特把15分解成了3和5的
乘积。当然，这只是非常初步的进展，我们还不知道，是否真的可以造出有实际价值的量
子计算机，量子态的纠缠非常容易退相干，这使得我们面临着技术上的严重困难。虽然
2002年，斯坦弗和日本的科学家声称，一台硅量子计算机是可以利用现在的技术实现的，
2003年，马里兰大学的科学家们成功地实现了相距0。7毫米的两个量子比特的互相纠缠，
一切都在向好的方向发展，但也许量子计算机真正的运用还要过好几十年才会实现。这个
项目是目前最为热门的话题之一，让我们且拭目以待。
就算强大的量子计算机真的问世了，电子安全的前景也并非一片黯淡，俗话说得好，
上帝在这里关上了门，但又在�