1700961939
上帝掷骰子吗？：量子物理史话（升级版） [:1700958648]
1700961940
Part. 3
1700961941
1700961942
电子计算机是人类有史以来最伟大的发明之一。自诞生那天以来，它已经深入到了我们生活的每一个方面，甚至彻底改变了整个世界的面貌。别的不说，各位正在阅读的本史话，最初便是在一台笔记本电脑上被输入和保存为电子信号的，虽然拿一台现代的PC仅仅做文字编辑可谓大材小用，或者拿Ian Stewart的话来说，算是开着劳斯莱斯送牛奶了。
1700961943
1700961944
回头看计算机的发展，人们往往会慨叹科技的发展一日千里。通常我们把宾夕法尼亚大学1946年的那台ENIAC看成世界上的第一台电子计算机(2) ，这是个异常笨重的大家伙，体积可以装满整个房间，塞满难看的电子管，输入输出都靠打孔的磁带。如果我们把它拿来和现代轻便精致的家庭电脑相比，就好像美女与野兽的区别。不过，从本质上来说，计算机自诞生以来却没有什么大变化，阿兰·图灵为它种下了灵魂，冯·诺伊曼为它雕刻了骨架，别的只是细枝末节罢了！
1700961945
1700961946
1700961947
1700961948
1700961949
量子计算机
1700961950
1700961951
在这个意义上来讲，美女与野兽其实是一样的，外表的色相差异只是一种错觉而已。我们如今所使用的电脑，不管看上去有多精巧复杂，本质上也没有脱出当年图灵和诺伊曼所画好的框框。把所有的计算机简化，它们都是这样一种机器：在一端读入信息数据流，按照特定的算法（有限的内态）来处理它，并在另一端输出结果。奔腾4、80286和ENIAC的区别也只不过在于处理的速度和效率而已。假如有足够的时间和输出空间，同作为图灵机，它们所能做到的事情是一样多的。对于传统的计算机来说，它处理的通常是二进制码信息，1个“比特”（bit，binary digit的缩写）是信息的最小单位，它要么是0，要么是1，对应于电路的开或关。假如一台计算机读入了10个bits的信息，那相当于说它读入了一个10位的2进制数（比方说1010101010），这个数的每一位都是一个确定的0或者1。如果你对计算机稍有认识的话，这些常识似乎是理所当然的。
1700961952
1700961953
但是，接下来就让我们进入神奇的量子世界。一个bit是信息流中的最小单位，这看起来正如一个量子！我们回忆一下走过的路上所见到的那些奇怪景象，量子论最叫人困惑的是什么呢？是不确定性。我们无法肯定地指出一个电子究竟在哪里，我们不知道它是通过了左缝还是右缝，我们不知道薛定谔的猫是死了还是活着。根据量子论的基本方程，所有的可能性都是线性叠加在一起的！电子同时通过了左和右两条缝，薛定谔的猫同时活着和死了。只有当实际观测它的时候，上帝才随机地掷一下骰子，告诉我们一个确定的结果，或者他老人家不掷骰子，而是把我们投影到两个不同的世界中去。
1700961954
1700961955
大家不要忘记，我们的电脑也是由微观的原子组成的，它当然也服从量子定律（事实上所有的机器肯定都是服从量子论的，只不过对于传统的机器来说，它们的工作原理并不主要建立在量子效应上）。假如我们的信息由一个个电子来传输，我们规定，当一个电子是“左旋”的时候，它代表了0，当它是“右旋”的时候，则代表1。现在问题来了，当我们的电子到达时，它是处于量子叠加态的。这岂不是说，它同时代表了0和1？
1700961956
1700961957
这就对了，在我们的量子计算机里，一个bit不仅只有0或者1的可能性，它更可以表示一个0和1的叠加！一个“比特”可以同时记录0和1，我们把它称作一个“量子比特”（qubit）。假如我们的量子计算机读入了一个10qubits的信息，所得到的就不仅仅是一个10位的二进制数了，事实上，因为每个bit都处在0和1的叠加态，我们的计算机所处理的是210 个10位数的叠加！
1700961958
1700961959
换句话说，同样是读入10bits的信息，传统的计算机只能处理1个10位的二进制数，而如果是量子计算机，则可以同时处理210 个这样的数！
1700961960
1700961961
利用量子演化来进行某种图灵机式的计算早在70年代和80年代初便由Bennett、Benioff等人进行了初步的讨论。到了1982年，那位极富传奇色彩的美国物理学家理查德·费曼（Richard Feynman）注意到，当我们试图使用计算机来模拟某些物理过程，例如量子叠加的时候，计算量会随着模拟对象的增加而指数式地增长，使得传统的模拟很快变得不可能。费曼并未因此感到气馁，相反，他敏锐地想到，也许我们的计算机可以使用实际的量子过程来模拟物理现象！如果说模拟一个“叠加”需要很大的计算量的话，为什么不用叠加本身去模拟它呢？每一个叠加都是一个不同的计算，当所有这些计算都最终完成之后，我们再对它进行某种幺正运算，把一个最终我们需要的答案投影到输出中去。费曼猜想，这在理论上是可行的，而他的确猜对了！
1700961962
1700961963
终于到了1985年，我们那位在埃弗莱特的谆谆教导和多宇宙论的熏陶下成长起来的大卫·德义奇闪亮登场了。他仿照图灵当年走的老路子，成功地证明了一台通用的量子计算机是可能的(3) ，这样一来，一切形式的量子计算便也都能够实现。德义奇的这个证明意义重大，他从理论上奠定了量子计算机的实现基础，一扇全新的门被打开了。
1700961964
1700961965
不过，说了那么多，一台量子计算机到底有什么好处呢？
1700961966
1700961967
德义奇证明，量子计算机无法实现超越算法的任务，也就是说，它无法比普通的图灵机做得更多。但他同时证明，它将具有比传统的计算机大得多的效率，用术语来讲，执行同一任务时它所要求的复杂性（complexity）要低得多。一言以蔽之，量子计算机虽然没法做得更多，但同样的任务却能做得更快更好！理由是显而易见的，量子计算机执行的是一种并行计算。正如我们前面举的例子，当一个10qubits的信息被处理时，量子计算机实际上操作了210 个态！
1700961968
1700961969
1700961970
1700961971
1700961972
大数分解加密的安全性
1700961973
1700961974
在如今这个信息时代，网上交易和电子商务的浪潮正席卷全球，从政府至平民百姓，都越来越依赖电脑和网络系统。与此同时，电子安全的问题也显得越来越严峻，谁都不想黑客们大摇大摆地破解你的密码，侵入你的系统篡改你的资料，然后把你银行里的存款提得精光，这就需要我们对隐私资料执行严格的加密保护。目前流行的加密算法不少，很多都是依赖于这样一个靠山，也即所谓的“大数不可分解性”。大家中学里都苦练过因式分解，也做过质因数分解的练习，比如把15这个数字分解成它的质因数的乘积，我们就会得到15=5×3这样一个唯一的答案。
1700961975
1700961976
问题是，分解15看起来很简单，但如果要分解一个很大很大的数，我们所遭遇到的困难就变得几乎不可克服了。比如，把10949769651859分解成它的质因数的乘积，我们该怎么做呢？糟糕的是，在解决这种问题上，我们还没有发现一种有效的算法。一种笨办法就是用所有已知的质数去一个一个地试，最后我们会发现10949769651859＝4220851×2594209(4) ，但这是异常低效的。更遗憾的是，随着数字的加大，这种方法所费的时间呈现指数式的增长！每当目标增加一位数，我们就要多费3倍多的时间来分解它，很快我们就会发现，就算计算时间超过宇宙的年龄，我们也无法完成这个任务。当然我们可以改进我们的算法，但目前所知最好的算法，它所需的复杂性也只不过比指数性的增长稍好，仍未达到多项式的要求(5) 。
1700961977
1700961978
所以，如果我们用一个大数来保护我们的秘密，只有当这个大数被成功分解时才会泄密，我们应当是可以感觉非常安全的。因为从上面的分析可以看出，想使用“暴力”方法，也就是穷举法来破解这样的密码几乎是不可能的。虽然我们的处理器速度每隔18个月就翻倍，但也远远追不上安全性的增长。只要给我们的大数增加一两位数，就可以保好几年的平安。目前最流行的一些加密术，比如公钥的RSA算法正是建筑在这个基础之上。
1700961979
1700961980
但量子计算机的实现使得所有这些算法在瞬间人人自危。量子计算机的并行机制使得它可以同时处理多个计算，这使得大数不再成为障碍！1994年，贝尔实验室的彼得·肖（Peter Shor）创造了一种利用量子计算机的算法，可以有效地分解大数（其复杂性符合多项式条件）。比如我们要分解一个250位的数字，如果用传统计算机的话，就算我们利用最有效的算法，把全世界所有的计算机都联网到一起联合工作，也要花上几百万年的漫长时间。但如果用量子计算机的话，只需几分钟！一台量子计算机在分解250位数的时候，同时处理了10500 个不同的计算！
1700961981
1700961982
更糟的事情接踵而来。在肖发明了他的算法之后，1996年贝尔实验室的另一位科学家洛弗·格鲁弗（Lov Grover）很快发现了另一种算法，可以有效地搜索未排序的数据库。如果我们想从一个有n个记录但未排序的数据库中找出一个特定的记录的话，大概只好靠随机地碰运气，平均试n/2次才会得到结果，但如果用格鲁弗的算法，复杂性则下降到根号n次。这使得另一种著名的非公钥系统加密算法DES显得岌岌可危。现在几乎所有人都开始关注量子计算，因为一旦量子计算机真的被制造出来，那现行的各种加密体系立刻就会面临崩溃。而最可怕的是，由于量子运算内在的并行机制，哪怕我们不断增加密钥的位数，也只不过给破解者增加很小的代价罢了，这些加密术实际上都破产了(6) ！
1700961983
1700961984
而话又说回来，破解密码，其实仅仅只是量子计算机可能的各种用途之一。利用量子的并行计算优势，我们完全可以用它来做更多酷炫的事。比如更准确地预报天气，更高效地开发药物，进行更强大的深度学习和人工智能开发，等等。因此，近十几年来，量子计算机已经成为科技界最为热门的话题之一，被认为是最有前途的开发领域，其发展速度之快也远远超乎人们的想象。
1700961985
1700961986
2011年，一家名叫D-Wave的加拿大公司发布了一个震惊世界的消息。他们宣称，自己已经造出了世界上第一台商用量子计算机，即D-Wave 1。不久后，著名的洛克希德·马丁公司向其购买了一台该机型，据说成交价高达1千万美元。2013年，该公司又推出了第二款型号D-Wave 2，并于2015年8月推出最新款D-Wave 2X，其芯片可以运行2048个qubits。NASA与Google都为此进行了购置并展开测试，据Google宣称，在一些特定的问题上，D-Wave 2X要比传统计算机芯片的运行速度快上1亿倍。
1700961987
1700961988
不过，D-Wave系列还不能算是通用的量子计算机，也不能运行所有的量子算法（比如Shor算法）。为此，世界各地的科学家们还在努力研究更一般的、具有更强大能力的原型机。当然，这其中显然会遇到极大的技术障碍，因为量子比特非常容易退相干，所以，未来的量子计算机究竟能到达什么样的程度，目前还不得而知。但毫无疑问，至少从理论上来说，我们完全可以从最小的量子中获得计算整个宇宙的能力。如果这一天真的到来，也许我们真的就可以跨过奇点，迈入一个完全无法想象的科技新时代。