1. 课程导入与量子计算全景
量子计算并不是“更快的经典计算机”，而是一类利用量子力学状态演化规律来组织计算过程的新型计算模型。理解这一点，是进入本课程的第一道门槛。经典计算机的基本单位是比特，只能处于 0 或 1；量子计算机的基本单位是量子比特（qubit），可以处于 |0⟩ 与 |1⟩ 的叠加态 α|0⟩+β|1⟩，其中 α、β 为复数且满足 |α|²+|β|²=1。多个量子比特还能形成纠缠，使整体状态无法拆成各比特状态的简单乘积。叠加与纠缠共同构成了量子算法获得优势的物理基础。
从发展脉络看，量子计算的思想萌芽于 20 世纪 80 年代：Feynman 提出用可控量子系统模拟量子物理过程，Benioff 与 Deutsch 探讨了量子图灵机模型。1994 年 Shor 提出大整数分解与离散对数量子算法，1996 年 Grover 提出无序数据库搜索的平方加速，这两项工作让“量子算法能带来实质加速”成为共识。此后，Deutsch-Jozsa、Bernstein-Vazirani、Simon 等算法构成了量子查询复杂度的经典教学序列，HHL 算法则开启了量子线性代数求解的方向。近十余年，超导、离子阱、光量子等硬件路线快速推进，量子纠错与容错阈值成为工程核心议题。
量子计算的核心优势可以归纳为三类来源。第一类是量子并行性：对 n 个量子比特施加 Hadamard 变换，可一次性制备 2ⁿ 个基态的等幅叠加，一次酉变换即同时作用于全部振幅。但必须强调，这并不等于“一次算出 2ⁿ 个答案”，因为测量只能得到一个结果，振幅中携带的信息必须通过干涉被“汇聚”到可观测的输出上。第二类是干涉与振幅放大：Grover 算法通过反复的“标记—扩散”操作，把目标态的振幅逐步放大、非目标态振幅压低，经约 (π/4)√N 次迭代后以高概率测得目标。第三类是纠缠与全局关联：在 Simon、Shor 等算法中，纠缠使寄存器之间形成经典难以复现的关联结构，配合量子傅里叶变换提取周期信息。
与此同时，量子计算的局限同样明确。其一是测量坍缩与不可克隆：无法复制未知量子态，也无法直接读取全部振幅，算法设计必须围绕“如何把有用信息转化为高概率测量结果”展开。其二是退相干与噪声：量子态极易受环境干扰，当前含噪中等规模量子（NISQ）设备需要大量重复采样与误差缓解。其三是线路深度与连通性限制：两比特门错误率通常比单比特门高一个量级，深线路在纠错前难以可靠执行。其四是问题适配性：量子优势并非普适，许多问题目前并无已知的量子加速，甚至量子算法所需的输入输出格式（如 QRAM、态制备）本身就可能成为瓶颈。
上图给出了本课程的主线结构。可以看到，Deutsch-Jozsa、Bernstein-Vazirani、Simon 属于量子查询复杂度序列，它们用“查询次数”这一清晰指标展示量子与经典的分离，是理解量子并行与干涉的最佳入口。Grover 属于搜索与振幅放大家族，其平方加速具有广泛的可组合性。Shor 属于周期提取家族，核心是量子傅里叶变换。HHL 则属于量子线性代数方向，其加速有严格的输入输出条件，是理解“量子优势边界”的典型样本。
本课程以“量子算法与经典算法对比”为主线，每一章都会围绕一个具体问题展开：先明确经典问题的定义与已知经典复杂度，再拆解量子算法的线路结构与关键步骤，最后比较两者的查询次数、时间复杂度、所需资源与适用条件。例如在 Grover 一章，我们会用 N=2²⁰（约 104 万）的示例说明：经典线性搜索最坏需约 104 万次比较，而 Grover 迭代次数约为 (π/4)√N ≈ 804 次，但每次迭代包含一次标记查询与一次扩散操作，且需重复采样以确认结果，实际总代价需按线路深度与采样次数折算。这类“理想加速”与“实际代价”的对照，将贯穿全课程。
需要提前建立的一个判断习惯是：量子算法的优势总是相对于某个经典基线而言的。同一个问题，经典算法可能已有多种复杂度不同的解法，量子算法比较的对象必须是当前最优或公认的经典基线，否则“加速”就失去意义。此外，量子算法通常输出的是概率分布或量子态，若问题要求输出完整的经典数据（例如列出全部解），量子优势可能被读出代价抵消。因此，在后续每一章中，我们都会同时关注“算法能做什么”和“它不能直接做什么”。
学习建议上，建议按“查询模型 → 搜索 → 周期提取 → 线性代数”的顺序推进，并在每章结束后手写一遍关键线路的矩阵形式或振幅演化。对于 Deutsch-Jozsa 与 Bernstein-Vazirani，可以先用 2 至 3 个量子比特手工推导；对于 Grover，建议用一个小规模 N（如 N=8）模拟迭代过程中目标态振幅的变化；对于 Shor，重点理解“分解问题如何归约为求阶问题”这一步，而不必一开始就陷入完整线路细节。掌握这条主线后，你将具备判断一个新问题是否值得尝试量子算法的基本框架。