Page 210 - 信息的脉络

·信息的脉络·
第七节 量子计算

尝试弄懂每件事情的一些情况，以及一些事情的每种情况。
——托马斯·赫胥黎

量子计算的故事始于 20 世纪 80 年代初，当时阿尔贡国家实验室的理论物理
学家保罗·贝尼奥夫提出了一个图灵机的量子力学模型，之后不久，理查德·费
曼在 1982 年在加利福尼亚大学伯克利分校发表了一场题为《用计算机模拟物理学》

的演讲中提出了量子计算机的基本概念。费曼对物理以及相关技术的远见卓识无
与伦比。费曼指出，“当普通计算机被用来给分子等量子力学对象建模时，他们
很难拿出充足的计算资源来追踪每件事，费曼猜测一台量子计算机可以完成这项
任务，因为它可以模拟量子世界的事物。”在演讲中，费曼谈到了使用计算机做
物理学模拟的问题：我对那些完全经典理论所做的分析感到不悦，因为自然并不“经

典”，如果你想模拟自然，那么你最好按照量子力学的规律去做，哎呀，这真是
一个好问题，因为它看起来并不那么容易。
费曼提议制造遵从量子力学规律的计算机：

你能使用新型计算机——量子计算机做量子力学模拟吗？它不是图灵机，而
是一种完全不同的机器。
自此以后，研究量子力学对计算机发展的制约就成为一个重要的学术领域，
并逐渐发现了如何利用量子力学的状态叠加和纠缠现象来进行计算。我们知道，

图灵机的基本原理是传统计算机运行的基础。而费曼提出的根据量子力学规律运
行的计算机，这种计算机能做传统计算机无法做的运算。费曼特别提到，使用量
子系统模拟来计算量子波函数和量子概率。1985 年，牛津大学物理学家戴维·多
伊奇（David Deutsch）进一步发展了量子计算理论，他指出，量子力学的叠加态

可以用来实现并行计算，在一台计算机中同时处理多组输入数据，并提议不要再
去追求摩尔定律的极限利用元件本身所服从的物理法则，就能更进一步。据此规
则能把信息书写在原子和亚原子等微观物理系统的量子态中，然后就可以运用量
子力学的标准定律来操控这些信息了。1985 年，多伊奇证明，做某些计算时量子

计算机的确可以比传统计算机快。但直到 1994 年，人们才真正对量子计算机感兴
趣，那时贝尔实验室的彼得·肖尔（Peter Shor）提出了一种量子算法（quantum
algorithm），使用量子算法解决某些数学问题比运行在传统计算机上的最好算法
还要快。而且算法的速度比经典算法有指数级的改进。这一发现重新唤起了人们

对量子计算机的兴趣，部分原因是，大数分解在密码学上有重要的意义。例如，
网络交易所需要的大众密码系统的安全，正是建立在大数分解的难计算性上。然

• 194 •