第一章 费曼的追问：量子计算的故事起源 / Chapter 1 Feynman's Question: The Origin Story of Quantum Computing

> 1981年5月，加州理工学院Feynman礼堂的落地窗被帕萨迪纳的梧桐影剪成碎块，台下坐着二十几位顶尖物理学家：有刚和费曼吵完架、正翻着白眼的沃尔夫冈·泡利，有坚持量子隐变量诠释的尼尔斯·玻尔的追随者，还有一群刚拿到博士学位的年轻研究者。讲台上的理查德·费曼穿了他标志性的花衬衫，口袋里塞着半包骆驼烟，上台前刚和身边的同事吐槽完经典计算机模拟量子系统的龟速——他前一天刚试图用克雷一号超级计算机模拟一个50个自旋的量子系统，跑了三天三夜，结果连能量收敛都没做到。他拿起粉笔，在黑板上写下了一个看似荒诞的问题：“难道我们不能用量子系统来模拟量子系统吗？” > > In May 1981, the floor-to-ceiling windows of Caltech's Feynman Lecture Hall were sliced into fragments by the shadows of Pasadena's plane trees, and more than two dozen top physicists sat in the audience: Wolfgang Pauli, who had just quarreled with Feynman and was rolling his eyes, followers of Niels Bohr who insisted on the quantum hidden variable interpretation, and a group of young researchers who had just received their PhDs. On the podium, Richard Feynman wore his signature Hawaiian shirt, with half a pack of Camel cigarettes stuffed in his pocket. Before going on stage, he had just complained to his colleagues about the slow speed of classical computer simulations of quantum systems—he had tried to use a Cray-1 supercomputer to simulate a 50-spin quantum system the day before, running for three days and nights, but failed to even achieve energy convergence. He picked up a piece of chalk and wrote a seemingly absurd question on the blackboard: "Can't we use quantum systems to simulate quantum systems?"

台下最初响起的是稀稀拉拉的轻笑，没人把这个穿着随意的“科学顽童”的话当回事——毕竟在过去半个世纪里，经典计算机已经是人类最强大的计算工具，从登月轨道计算到核武器模拟，没有它搞不定的问题。但只有极少数人注意到，费曼在黑板上写下的这句话，刚好踩中了经典计算的天花板，也踩中了量子力学最核心的奥秘。

1.1 经典计算的边界：指数墙前的绝望 / 1.1 The Boundary of Classical Computing: Despair Before the Exponential Wall

要理解费曼当时的追问到底有多颠覆，我们首先得回到1981年的计算技术现实，搞清楚经典计算机到底为什么模拟不了量子系统。

经典计算机的核心是图灵机模型：它的存储单元是比特（bit），每个比特只能处于0或1的确定状态，n个比特的存储空间最多可以表示$2^n$种不同的状态，但同一时间只能处于其中一种。而量子系统的状态完全不同：一个量子比特可以处于$|0\rangle$和$|1\rangle$的叠加态，n个量子比特的状态是$2^n$维希尔伯特空间（Hilbert space）中的一个向量，同一时间可以同时处于所有$2^n$个基态的叠加中。

这种差异直接导致了经典计算机模拟量子系统的“指数墙（exponential wall）”问题：要完整描述n个量子比特的状态，经典计算机需要存储$2^n$个复数振幅，每个复数通常需要8字节的实部和8字节的虚部，也就是16字节的存储空间。也就是说，模拟n个量子比特需要的存储空间是： $$ S(n) = 16 \times 2^n \text{ 字节} $$

这个公式看起来不起眼，但指数增长的恐怖之处在于，只要n增加1，存储需求就会翻一倍。我们来看几个具体的例子：

• 模拟10个量子比特：$S(10) = 16 \times 2^{10} = 16 \text{ KB}$，现在的手机都能轻松搞定；
• 模拟20个量子比特：$S(20) = 16 \times 2^{20} = 16 \text{ MB}$，和一张高清照片差不多大；
• 模拟30个量子比特：$S(30) = 16 \times 2^{30} = 16 \text{ GB}$，需要一台高性能个人电脑；
• 模拟40个量子比特：$S(40) = 16 \times 2^{40} = 16 \text{ TB}$，已经接近顶级超级计算机的存储上限；
• 模拟50个量子比特：$S(50) = 16 \times 2^{50} \approx 16 \text{ PB}$（拍字节），也就是16000 TB，是1981年最先进的克雷一号超级计算机（最大存储8 MB）的200万倍。

<aside class="sidebar">

侧边栏：什么是希尔伯特空间？

希尔伯特空间是量子力学的数学核心基础，你可以把它理解成一个“无限维度的向量空间”：每一个量子系统的状态都是这个空间中的一个点，而量子系统的演化就是这个点在这个空间里的移动。对于n个量子比特组成的系统，这个空间的维度是$2^n$，也就是n个比特的所有可能组合的数量。经典计算机只能存储这个空间里的一个点，而量子计算机可以通过叠加态，同时“感知”整个空间的所有点——这也是量子计算优势的根源。 </aside>

1981年的现实是，连模拟一个只有50个量子比特的简单量子系统，经典计算机都需要200万倍的存储扩容，而真实的量子系统比如一个水分分子，就有10个电子、3个原子核，相当于几十个量子比特的相互作用；一个中等大小的蛋白质分子，有上千个原子，对应的量子系统维度是$2^{1000}$，这个数字比宇宙中的原子总数（约$10^{80}$）还要大得多，经典计算机哪怕把整个宇宙的所有物质都做成存储单元，也存不下这个波函数。

费曼当时正陷在这样的困境里：他是量子电动力学（QED）的奠基人之一，日常需要计算粒子之间的相互作用，而粒子相互作用本质上是量子系统的演化，经典计算机的模拟速度慢到几乎无法用于实际研究。他试过各种优化算法，比如微扰论、密度泛函理论，但这些方法都有局限性，只能处理非常简单的系统，稍微复杂一点就会出错。他知道问题的根源不在算法，而在计算框架本身：经典计算机是经典的，而自然本质上是量子的，用经典的工具去模拟量子的世界，就像用尺子去测量光速，框架本身就是错的。

这种切肤之痛让费曼在演讲中抛出了那个改变历史的问题：“自然不是经典的，该死的，如果你想模拟自然，你最好让它成为量子力学的，这就是量子计算机的idea。” > "Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy." > ——理查德·费曼，1981年加州理工学院演讲

1.2 “用量子系统模拟量子系统”：费曼的革命性直觉 / 1.2 "Simulating Quantum Systems with Quantum Systems": Feynman's Revolutionary Intuition

费曼的这句话听起来像一句玩笑，但背后是他几十年来对量子力学本质的思考沉淀。要理解这个直觉的颠覆性，我们得回到他年轻时的经历——1935年，24岁的费曼前往哥本哈根拜访量子力学的奠基人尼尔斯·玻尔，讨论量子力学的完备性问题。

当时的物理学界正陷在“量子力学是不是完备”的大论战里：爱因斯坦、玻尔、薛定谔等人吵了十几年，核心分歧是量子力学的概率诠释是不是对的。玻尔坚持认为量子力学是完备的，微观粒子的状态本来就是概率性的，不存在确定的轨迹；而以爱因斯坦为首的反对派则认为量子力学不完备，存在被隐藏的“隐变量”，只要找到这些变量，就能像经典物理一样，精确预测粒子的状态。费曼当时站在玻尔这边，但他和玻尔的争论从来不是盲从，而是基于对量子现象的深刻理解。

在哥本哈根的七天里，费曼和玻尔吵了无数次，最激烈的争论是关于双缝干涉实验：如果 electron 真的像玻尔说的那样，同时穿过两条缝，那为什么我们观测的时候，它只会出现在一条缝的位置？玻尔的回答是“观测行为本身会干扰系统”，费曼则反驳说“那你的解释只是把问题推给了观测者，并没有解决本质问题”。最后两人不欢而散，费曼临走前玻尔跟他说：“你太年轻了，还不懂量子力学的奥秘。”费曼后来回忆说，那次争论让他第一次意识到，经典物理的直觉在量子世界里完全没用，你不能用“粒子要么在这里要么在那里”的经典逻辑去理解量子世界，量子世界的本质是叠加、是概率、是整体的关联。

这种认知成了费曼后来思考量子计算的核心基础：如果经典计算机的逻辑是经典的，那用量子系统的逻辑来构建计算机，不就可以完美模拟量子世界了吗？这个想法听起来简单，但当时没有任何人往这个方向想过——在1981年，量子力学已经被创立了半个世纪，但所有人都默认“计算”是经典物理的范畴，量子力学只是用来描述微观粒子的理论，和计算没有任何关系。费曼的颠覆性在于，他把量子力学从“描述世界的理论”变成了“构建计算工具的基础”。

但费曼当时并没有立刻构建出一个完整的量子计算模型，他只是提出了这个核心设想，剩下的工作留给了后来的研究者。他在演讲的最后说：“这个问题的难度不在于量子力学的部分，而在于如何把量子系统的演化转换成我们可以控制的计算步骤。如果有人能解决这个问题，那将会是一个伟大的突破。”这句话刚好给后来的研究者指明了方向。

1.3 从灵感到模型：Benioff与量子图灵机的诞生 / 1.3 From Inspiration to Model: Benioff and the Birth of the Quantum Turing Machine

费曼的演讲在当时并没有引起太大的轰动，毕竟“用量子系统模拟量子系统”听起来还是太天马行空了。但演讲的内容刚好被当时在普林斯顿高等研究院访问的IBM物理学家保罗·本尼奥夫（Paul Benioff）听到了。

本尼奥夫当时的研究方向是量子化学，他的日常工作就是用量子力学的方法计算分子的电子结构，和费曼一样，他也被经典计算机的模拟速度折磨得苦不堪言。他听完费曼的演讲之后，立刻意识到这个想法的可行性：如果能把图灵机的存储单元换成量子比特，把图灵机的演化规则换成量子力学的幺正演化（unitary evolution），那不就可以实现一个能模拟量子系统的量子图灵机了吗？

本尼奥夫花了两年时间，把这个想法变成了严格的数学模型。1982年，他在《物理评论快报》（Physical Review Letters）上发表了题为《图灵机的量子力学哈密顿量模型》（*Quantum Mechanical Hamiltonian Models of Turing Machines*）的论文，首次提出了量子图灵机的严格定义： 1. 存储单元：经典图灵机的存储单元是比特，只能处于0或1的状态；量子图灵机的存储单元是量子比特，可以处于$|0\rangle$、$|1\rangle$的叠加态，甚至多个量子比特的纠缠态。 2. 演化规则：经典图灵机的每一步演化都是确定性的逻辑操作；量子图灵机的每一步演化都是幺正变换，也就是量子力学的哈密顿量演化，保证状态的归一化（总概率为1）和信息不丢失。 3. 可观测性：量子图灵机的最终状态可以通过测量得到经典的计算结果，测量过程会使得叠加态坍缩到某一个基态，得到确定的输出。

这个模型第一次严格证明了：量子系统确实可以实现通用计算，只要没有外界干扰，量子图灵机可以模拟任何经典图灵机可以模拟的过程，甚至可以模拟量子系统本身。本尼奥夫的论文发表之后，立刻引起了物理学界的关注，但也招来了很多质疑。

最大的质疑来自“退相干（decoherence）”问题：量子系统的叠加态非常脆弱，只要和外界环境发生微小的相互作用（比如一个光子的碰撞、一个原子的热振动），就会立刻坍缩到经典状态，失去量子特性。当时的物理学家认为，现实中的量子系统根本不可能保持足够长时间的叠加态来完成计算，量子图灵机只是一个数学上的玩具，不可能在现实中实现。

本尼奥夫当时没有办法解决退相干的问题，他只能在自己的论文里假设量子系统是完全孤立的，没有外界干扰。但这个质疑并没有否定量子图灵机的理论价值，它只是指出了实现量子计算的技术难点——这个难点直到20多年后才被量子纠错理论解决。

<aside class="sidebar">

侧边栏：什么是幺正演化？

幺正演化是量子力学的基本演化规则，指的是量子系统的状态变化由一个幺正矩阵（满足$U^\dagger U = I$，其中$U^\dagger$是U的共轭转置，I是单位矩阵）来描述。幺正变换的核心性质是保持状态的内积不变，也就是保证概率的归一化：量子系统在任何时候处于所有可能状态的概率之和都是1，不会出现概率丢失或者凭空产生的情况。这也是量子计算不会丢失信息、可以反向计算的理论基础。 </aside>

1.4 量子线路的雏形：Deutsch构建通用计算框架 / 1.4 The Prototype of Quantum Circuits: Deutsch Builds a Universal Computing Framework

本尼奥夫的量子图灵机模型虽然严格证明了量子计算的理论可行性，但它有一个很大的局限性：它的演化是基于哈密顿量的连续演化，很难对应到实际的计算步骤，也很难扩展成通用的计算模型。这个局限性在1985年被一位牛津大学的年轻博士生戴维·多伊奇（David Deutsch）解决了。

多伊奇当时的研究方向是量子力学的 foundations，他看了费曼的演讲和本尼奥夫的论文之后，意识到量子图灵机模型的核心价值，但也发现了它的不足：本尼奥夫的模型只能模拟量子系统的哈密顿量演化，不能模拟任意的计算过程，比如经典的逻辑运算、条件判断这些，都没法直接对应到量子图灵机的演化规则里。他想构建一个更通用的量子计算模型，不仅能模拟量子系统，还能完成任何经典计算机能完成的计算，甚至完成经典计算机做不到的计算。

多伊奇的核心贡献有两个：第一，他提出了通用量子图灵机的严格定义，证明了只要有一个通用的量子图灵机，就可以模拟任何其他量子图灵机的演化过程，就像经典图灵机的通用性一样；第二，他提出了量子线路模型（quantum circuit model），把量子图灵机的连续演化拆解成离散的量子门操作，就像经典计算机的逻辑门一样，把量子计算从抽象的数学模型变成了可以实际操作的工程框架。

量子线路模型的核心思路是：任何一个量子比特的幺正变换，都可以拆解成一系列基本的量子门的组合，就像任何经典的逻辑运算都可以拆解成与、或、非门的组合一样。多伊奇证明了，只要有一组通用的量子门（比如单比特的任意幺正变换和双比特的受控非门），就可以组合出任何可能的量子变换，实现通用的量子计算。这个模型现在是量子计算的主流模型，我们后面讲的所有量子算法，都是基于量子线路模型来构建的。

多伊奇的工作还有一个更重要的价值：他第一次证明了量子计算确实比经典计算有优势。1992年，他和理查德·乔萨（Richard Jozsa）提出了Deutsch-Jozsa算法，这是一个非常简单的算法：给定一个黑盒函数，这个函数要么是常数函数（所有输入的输出都一样），要么是平衡函数（一半输入输出0，一半输入输出1），经典计算机最坏情况需要查询$2^{n-1}+1$次才能确定函数的类型，而Deutsch-Jozsa算法只需要查询1次就能得到结果。这是人类历史上第一个证明量子计算有严格优势的算法，虽然它没有实际应用价值，但它证明了量子计算不是“更快一点的经典计算”，而是完全不同的计算范式。

多伊奇后来回忆说，他当时去找费曼讨论这个想法的时候，费曼刚开始还觉得太复杂，说“你为什么不用量子线路来构建模型？那样更简单”，多伊奇回去之后就把量子线路模型做出来了，费曼知道之后还跟别人吐槽“我本来想自己做的，被他抢先了”。这个轶事后来成了量子计算领域的经典故事，也体现了费曼作为“科学顽童”的可爱之处。

1.5 质疑与曙光：量子计算从边缘走向主流 / 1.5 Doubt and Dawn: Quantum Computing Moves from the Margins to the Mainstream

从1981年费曼的演讲到1995年，量子计算在物理学界经历了长达15年的边缘化。当时的绝大多数物理学家都觉得，量子计算只是一个有趣的数学玩具，不可能在现实中实现，更不可能有任何实际应用价值。质疑的声音来自方方面面：

• **理论质疑**：很多物理学家认为，量子计算的测量坍缩问题根本无法解决，你没法从叠加态的测量结果里得到有用的信息，因为每次测量得到的结果都是随机的；
• **技术质疑**：退相干问题看起来是无解的，没有任何材料可以保证量子比特的叠加态维持足够长的时间来完成计算；
• **价值质疑**：就算量子计算能实现，又能做什么？当时唯一知道的量子算法就是Deutsch-Jozsa算法，没有任何实际应用场景，根本看不出比经典计算强在哪里。

这种边缘化的状态一直持续到1994年，当时贝尔实验室的彼得·肖尔（Peter Shor）提出了Shor算法，证明量子计算机可以在多项式时间内完成大整数的分解，而这个问题是经典计算机最难解决的问题之一，目前没有已知的多项式时间算法。大整数分解是RSA加密算法的核心基础，RSA加密现在被广泛用于银行、军事、互联网的加密通信，如果量子计算机可以快速分解大整数，那现在的所有RSA加密都会在瞬间被破解。这个结果一出来，整个科学界和工业界都震动了：原来量子计算不是玩具，它可以直接颠覆现有的信息安全体系。

肖尔算法的出现让量子计算从理论玩具变成了实