第一章 量子计算导论：从经典计算到量子范式

自20世纪40年代阿兰·图灵提出图灵机理论模型、约翰·冯·诺依曼确立现代计算机体系结构以来，经典计算技术经历了从电子管、晶体管到超大规模集成电路的多次迭代，摩尔定律在过去半个多世纪里持续驱动着计算能力的指数级增长，智能手机、超级计算机等经典计算设备已经深度融入人类的生产生活。然而进入21世纪后，经典计算的物理瓶颈愈发凸显：当晶体管制程逼近3纳米甚至更小的尺度时，量子隧穿效应导致晶体管漏电严重，功耗与发热问题难以突破，摩尔定律的逐步失效已成为半导体行业的共识。与此同时，人类在诸多前沿科学领域面临的复杂问题，如新材料研发中的多体量子系统模拟、药物研发中的蛋白质折叠模拟、密码学中的大数质因数分解、金融领域的复杂组合优化等，经典计算机受限于其串行运算和确定性信息表示方式，要么需要耗费数千年甚至更长时间才能完成计算，要么根本无法完成有效求解。正是在这样的背景下，基于量子力学原理构建的量子计算，作为一种全新的计算范式，自20世纪80年代被提出以来，逐渐成为全球科技竞争的焦点领域。

量子计算的理论起源可以追溯到1982年，诺贝尔物理学奖得主理查德·费曼在演讲《Simulating Physics with Computers》中首次明确提出：由于经典计算机的比特状态是确定的，无法高效模拟遵循量子力学规律的量子系统的演化过程，而量子系统本身天然具备量子态的描述能力，因此构建基于量子力学原理的计算机，是模拟量子系统的最自然方式。这一观点首次揭示了量子计算的核心价值——量子模拟，也为量子计算的发展奠定了理论基础。1985年，牛津大学的大卫·多伊奇在费曼工作的基础上，提出了量子图灵机模型，证明了量子计算机可以实现任何经典计算机能够实现的计算功能，即量子计算对经典计算具有通用性，同时首次从理论上证明了量子计算相比经典计算存在潜在的加速优势。1994年，贝尔实验室的彼得·肖尔提出了著名的Shor算法，证明了量子计算机可以在多项式时间内完成大数的质因数分解，而这一问题在经典计算框架下属于NP难问题，目前没有已知的多项式时间算法，Shor算法的提出直接击碎了当时广泛使用的RSA公钥加密体系的安全性基础，引发了全球对量子计算的广泛关注。1996年，洛夫·格罗弗提出了Grover无序数据库搜索算法，证明了量子计算机可以在$O(\sqrt{N})$的时间内完成无序数据库的搜索，相比经典算法的$O(N)$时间复杂度实现了二次加速，进一步拓展了量子计算的应用场景。

在理论框架逐步完善的同时，量子计算的实验验证也在不断突破。1998年，IBM、牛津大学等团队首次实现了2量子比特的量子逻辑门操作，证明了量子门操控的可行性。2001年，IBM团队首次在7量子比特的核磁共振量子计算机上实现了Shor算法，成功分解了数字15的质因数，验证了量子算法的理论正确性。2019年，谷歌宣布其53量子比特的超导量子处理器“悬铃木”（Sycamore）实现了“量子霸权”：即针对一个专门设计的随机电路采样任务，悬铃木仅用了200秒就完成了计算，而当时世界上最快的经典超级计算机“顶点”（Summit）需要约1万年才能完成相同任务，这是人类历史上首次在特定任务上证明量子计算的计算能力超越经典计算。2023年，IBM发布了1121量子比特的“Condor”处理器，同时展示了量子纠错的最新进展，证明了随着量子比特数量的提升和纠错能力的增强，量子计算的实用化进程正在不断加速。我国在量子计算领域也取得了诸多突破，2021年中国科学技术大学研制的“祖冲之二号”超导量子处理器实现了62量子比特的可编程计算，2023年推出的“九章三号”光量子计算原型机在处理高斯玻色采样任务上的性能比经典超级计算机快一亿亿倍，这些成果标志着我国量子计算研究已经处于全球第一梯队。

量子计算是一种遵循量子力学规律，通过操纵量子比特（Qubit）完成信息处理的计算技术。与经典计算以经典比特为信息载体不同，量子计算的核心信息单元是量子比特，其最本质的特征是叠加性、纠缠性和相干性。经典比特在任何时刻只能处于0或1的确定状态，其信息表示可以用二进制数$b \in \{0,1\}$描述，1个经典比特只能承载1比特的信息。而量子比特可以同时处于0态和1态的相干叠加，其量子态可以用狄拉克符号表示为： $$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$$ 其中$|0\rangle$和$|1\rangle$是量子比特的两个本征态，对应经典比特的0和1状态，$\alpha$和$\beta$是复数，称为概率幅，满足归一化条件$|\alpha|^2 + |\beta|^2 = 1$。当对量子比特进行测量时，会以$|\alpha|^2$的概率得到0，以$|\beta|^2$的概率得到1，测量后量子态会坍缩到对应的本征态。这里需要特别说明的是，量子叠加态并非经典概率意义上的“既处于0又处于1的混合状态”，而是两个本征态的相干叠加，这种相干性使得量子比特可以同时承载多个状态的信息，这是量子计算并行性的物理基础。n个量子比特的张量积会形成一个$2^n$维的希尔伯特空间，其叠加态可以同时承载$2^n$个基态的相干信息，这是量子计算指数级加速潜力的来源之一。

量子纠缠是量子力学最反直觉的特性之一，当两个或多个量子比特发生相互作用后，可能形成一个不可分割的整体系统，其量子态无法表示为单个量子比特态的直积形式，这种状态称为纠缠态。最典型的两量子比特纠缠态是贝尔态： $$|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$$ 对于贝尔态，当对其中一个量子比特进行测量得到0时，另一个量子比特的状态会瞬间坍缩到0；如果测量得到1，另一个会瞬间坍缩到1，无论两个量子比特之间的距离有多远。爱因斯坦将这种现象称为“幽灵般的超距作用”，但需要明确的是，量子纠缠无法实现超光速信息传输：因为纠缠态中单个量子比特的测量结果是完全随机的，无法被人为操控，因此无法通过纠缠传递有效信息，这并不违背相对论的光速限制。

量子相干性是量子比特保持叠加态和纠缠态的前提，当量子系统与外界环境发生相互作用时，会发生退相干现象，导致量子态的相位信息丢失，叠加态坍缩为经典的混合态，量子计算的优势也随之消失。退相干是当前量子计算面临的最核心的挑战之一，提升量子比特的相干时间是当前量子计算研究的重点方向之一。

经典计算与量子计算在信息载体、运算规则、计算能力三个维度上存在本质差异，这些差异直接决定了量子计算的独特优势。从信息载体来看，经典比特的状态是确定的、离散的，每个经典比特只能承载1比特的信息，n个经典比特只能表示$2^n$种状态中的一种；而量子比特的状态是概率性的、连续的，n个量子比特的叠加态可以同时承载$2^n$个基态的相干信息，但这种“同时承载”并非经典意义上的并行存储，而是量子态的相干叠加，只有通过量子干涉等操作才能将多个状态的信息提取出来。二者的核心特性对比如下：

| 特性 | 经典比特 | 量子比特 | |--------------|------------------------------|------------------------------| | 状态表示 | 确定性的0或1 | 概率幅叠加的$\alpha|0\rangle+\beta|1\rangle$ | | 信息承载能力 | 1比特/个 | n个量子比特可承载$2^n$维希尔伯特空间的相干信息 | | 状态演化 | 布尔逻辑运算，多数不可逆 | 幺正变换，完全可逆 | | 测量结果 | 确定，不改变原有状态 | 随机，导致态坍缩到对应本征态 |

从运算规则来看，经典计算的运算基于布尔代数，通过逻辑门（与门、或门、非门等）对经典比特进行操作，布尔运算的本质是将输入比特映射到确定的输出比特，且大部分逻辑门是不可逆的（比如与门，输入两个1得到1，无法从输出反推输入）。而量子计算的运算基于量子力学的幺正演化，通过量子门对量子比特进行操作，量子门对应幺正矩阵，满足$U^\dagger U = UU^\dagger = I$（其中$U^\dagger$是U的共轭转置，I是单位矩阵）。幺正变换的核心特性是保持量子态的归一化条件和内积不变，即保证量子态的演化是可逆的，且不会丢失信息。此外，量子门的作用是改变量子态的概率幅的相位和幅值，通过设计不同的量子门序列，可以实现对量子态的任意幺正变换，这是量子算法实现加速的核心操作基础。对于任意两个量子态$|\psi\rangle$和$|\phi\rangle$，幺正变换U满足$\langle U\psi | U\phi \rangle = \langle \psi | \phi \rangle$，说明变换前后两个态的内积不变，即态的“相似性”被保留，这一特性是量子计算保持信息完整性的物理基础。

从计算能力来看，经典计算的计算能力受限于摩尔定律和串行运算的瓶颈，对于特定类型的复杂问题，经典计算的时间复杂度往往随着问题规模的增大呈指数级增长，无法在合理时间内完成求解。而量子计算通过叠加性、纠缠性和量子干涉的特性，可以对特定问题实现指数级或多项式级的加速。这里需要特别澄清一个常见的误解：很多人认为量子计算的加速来自于“同时计算所有可能的状态”，这种表述是不准确的。n个量子比特的叠加态确实包含$2^n$个基态的相干叠加，但如果只是简单地对所有基态进行并行计算，测量时只会得到一个随机的结果，无法得到问题的解。量子加速的真正来源是量子算法对量子干涉的巧妙利用：由于概率幅是复数，具有相位属性，当两个概率幅的相位相反时，它们的和会相互抵消（相消干涉），当相位相同时会相互增强（相长干涉）；通过量子门的操作，可以让代表错误答案的概率幅相互抵消，让代表正确答案的概率幅相互增强，从而在测量时以极高的概率得到正确答案，这种概率幅的调控是经典计算无法实现的。

为了帮助初学者直观理解量子加速的效果，本章介绍三个典型的量子算法案例。第一个是Deutsch-Jozsa算法：该问题要求判断一个黑箱函数$f: \{0,1\}^n \rightarrow \{0,1\}$是常函数（所有输入对应的输出相同）还是平衡函数（恰好一半输入对应输出0，另一半对应输出1）。经典计算机在最坏情况下需要查询$2^{n-1}+1$次函数才能确定结果，而量子计算机只需要查询1次就可以得到确定结果，实现了指数级加速。虽然该算法本身没有直接的实际应用价值，但清晰地

虽然该算法本身没有直接的实际应用价值，但清晰地验证了量子并行性与量子干涉的加速潜力，是量子计算领域第一个具有明确指数级加速优势的理论算法。接下来我们通过具体案例进一步阐释量子加速的物理根源。

Deutsch-Jozsa算法的具体实现过程可以直观展现量子计算的独特优势：假设n=1，即待判断的黑箱函数$f: \{0,1\} \rightarrow \{0,1\}$的输入输出均为1比特，常函数的定义是$f(0)=f(1)$，平衡函数的定义是$f(0) \neq f(1)$。经典计算机在最坏情况下需要查询2次函数才能确定其类型：若第一次查询$f(0)=0$，则必须第二次查询$f(1)$才能确认是常函数还是平衡函数，无法通过1次查询得到确定结论。而量子计算机仅需1次查询即可得到100%准确的结论：首先制备一个处于叠加态$|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$的输入量子比特，再制备一个辅助量子比特处于$|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$态，将黑箱函数实现为量子oracle门$U_f$，其作用为$U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$（其中$\oplus$表示异或运算）。当叠加态输入oracle门后，量子态的相位会携带$f(x)$的全局属性：若$f$是常函数，则叠加态的相位保持不变；若$f$是平衡函数，则两个基态的相位会发生相对翻转。随后通过哈达玛门（H门，作用为$H|0\rangle=|+\rangle, H|1\rangle=|-\rangle$）进行干涉操作，最后测量输入量子比特，会以100%的概率得到0（对应常函数）或1（对应平衡函数）。当输入维度n增大时，经典计算机的查询次数呈指数级增长（最坏情况为$2^{n-1}+1$次），而量子计算机始终仅需1次查询，这种指数级的加速差异直观地展现了量子计算相比经典计算的独特优势。

除了Deutsch-Jozsa算法外，另外两个标志性算法进一步拓展了量子计算的应用边界。1996年提出的Grover无序数据库搜索算法，针对在N个元素的无序数据库中查找特定目标的问题，经典算法的最坏时间复杂度为$O(N)$，平均需要查询$\frac{N}{2}$次；而Grover算法通过量子振幅放大技术，仅需$O(\sqrt{N})$次查询即可找到目标，实现了二次加速。以包含100万个条目的数据库为例，经典算法平均需要查询50万次，而Grover算法仅需约1000次即可完成搜索，这种加速优势在密码破译、数据检索、组合优化等领域具有极高的应用价值。1994年提出的Shor算法则是量子计算最知名的应用之一，该算法可以在多项式时间$O(n^3)$内完成n位大数的质因数分解，而目前经典计算机最优秀的质因数分解算法（数域筛法）的时间复杂度为$O(e^{(64/9)^{1/3} n^{1/3} (\log n)^{2/3}})$，呈亚指数级增长。以目前广泛使用的2048位RSA加密密钥为例，经典超级计算机需要数十亿年才能完成分解，而足够规模的容错量子计算机仅需数小时甚至数分钟即可完成，这一特性直接威胁当前主流的公钥加密体系的安全性，推动了全球抗量子密码（PQC）的研究与标准化进程。

上述算法的加速能力并非来自量子计算对所有问题的普遍加速，而是来自量子力学特性与特定问题结构的深度契合。为了更清晰地理解经典计算与量子计算的核心差异，我们可以从信息处理的全流程进行对比：经典计算的信息处理流程是“确定输入→串行逻辑运算→确定输出”，每个操作都是对确定状态的变换；而量子计算的信息处理流程是“叠加态初始化→幺正演化（量子门操作）→量子测量坍缩”，其核心差异体现在三个层面：

第一，信息表示方式的差异。经典比特是二进制的确定状态，n个经典比特的态空间是离散的$2^n$维空间的单个点，只能表示一个确定的状态；而n个量子比特的态空间是连续的$2^n$维希尔伯特空间，叠加态可以同时表示所有基态的相干叠加。这里需要特别澄清一个常见误解：很多人认为“n个量子比特可以同时存储$2^n$个经典比特的信息”，这种表述是不准确的。量子比特的叠加态虽然包含$2^n$个基态的相干信息，但由于量子测量的随机性，单次测量只能得到n比特的确定结果，其可提取的经典信息量上限仍然是n比特。量子计算的优势并非来自“存储更多信息”，而是来自对全局信息的相干操控：通过幺正变换，量子门可以同时作用在所有叠加态上，通过对概率幅相位的全局调控，实现经典计算无法实现的并行信息处理。我们可以通过一个具体的例子理解这一差异：1个经典比特只能处于$|0\rangle$或$|1\rangle$中的一种状态，而1个量子比特可以处于$\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$的叠加态；2个经典比特只能处于$|00\rangle, |01\rangle, |10\rangle, |11\rangle$中的一种状态，而2个量子比特可以处于$\frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$的叠加态，同时承载4个基态的相干信息。当对2量子比特叠加态施加一个X门（非门，作用为$X|0\rangle=|1\rangle, X|1\rangle=|0\rangle$）时，相当于同时对所有4个基态执行非门操作，得到$\frac{1}{2}(|11\rangle + |10\rangle + |01\rangle + |00\rangle)$，这种对多个状态的并行操作是量子计算并行性的来源。

第二，运算逻辑的差异。经典计算的逻辑门基于布尔代数，是不可逆的：比如与门（AND）将两个输入比特映射为一个输出比特，输入信息存在丢失，无法从输出反推输入；或门（OR）、非门（NOT）等基础逻辑门也都是不可逆的。而量子门基于幺正变换，是完全可逆的：每个量子门都对应一个幺正矩阵$U$，满足$U^\dagger U = UU^\dagger = I$（其中$U^\dagger$是U的共轭转置，I是单位矩阵），其逆矩阵就是自身的共轭转置，因此量子计算的过程不会丢失任何信息，输入态可以通过逆量子门完全恢复。这种可逆性不仅符合量子力学的演化规律，也为量子纠错提供了理论基础。此外，经典逻辑门的操作是确定性的，输入确定则输出一定确定；而量子门的操作是幺正的，输入叠加态则输出也是叠加态，其作用是改变概率幅的相位和幅值，而非直接得到计算结果。

第三，问题求解逻辑的差异。经典计算求解问题的逻辑是“分步迭代”：对于复杂问题，往往需要将问题拆解为多个子步骤，逐步求解，最终

经典计算求解问题的逻辑是“分步迭代”：对于复杂问题，往往需要将问题拆解为多个子步骤，逐步求解，最终通过每一步的确定输出得到最终结果。以经典计算机分解15的质因数为例，需要依次尝试2、3、4……直到根号15≈3.87，共需3次试除操作，每一步只能处理一个候选因子，无法同时处理所有可能的因子。而量子计算求解问题的逻辑是“全局相干操控”：通过初始化叠加态同时承载所有可能的输入状态，通过幺正变换对所有叠加态进行并行操作，再通过量子干涉放大正确答案的概率幅，最后通过单次测量得到高概率的正确结果。以Shor算法分解15为例，量子计算机仅需通过量子傅里叶变换同时处理所有可能的周期信息，一次幺正变换即可得到函数$f(x)=2^x \mod 15$的周期r=4，随后通过经典计算即可得到质因数3和5，无需逐个试除。

这种求解逻辑的差异直接决定了二者在适用场景上的本质区别：经典计算擅长处理确定性、规则明确的通用计算任务，如文档处理、网页浏览、数值计算等，其优势在于稳定性高、能效比高、软件生态完善；而量子计算擅长处理具有量子特性、高复杂度、搜索空间庞大的特定问题，如量子系统模拟、大数质因数分解、无序数据库搜索、组合优化等，其优势在于对特定问题可实现指数级或多项式级加速。二者并非替代关系，而是互补关系：未来的计算架构将是“经典计算机+量子协处理器”的混合架构，经典计算机负责通用的逻辑控制和数据预处理，量子协处理器负责处理特定类型的复杂任务，二者通过高速接口进行数据交互。

<标签：算法案例>

典型量