1. 课程导入与全景认知
当我们谈论“量子计算机比经典计算机快多少”时，真正决定答案的并不是量子比特的数量，而是算法在问题规模增长时所需资源的增长速度。这正是计算复杂度研究的核心。量子计算复杂度与资源估算，研究的是：给定一个计算任务，在量子计算模型下，完成它最少需要多少时间、多少量子比特、多少量子门、多少纠错开销，以及这些量随问题规模如何变化。它既回答“理论上能不能高效做到”，也回答“工程上要付出多大代价才能做到”。
要理解这门课，先要区分三个经常被混用的层次。第一层是计算模型：量子线路模型、绝热量子计算、量子游走、量子图灵机等，它们定义了“允许做什么操作”。第二层是复杂度类：BQP、QMA、QCMA、BPP、NP 等，它们刻画“在给定资源约束下问题属于哪一类”。第三层是资源估算：把抽象算法落到具体硬件上，算出逻辑量子比特数、T 门数量、电路深度、所需物理量子比特与运行时间。三者层层递进：模型决定可表达的操作，复杂度类给出渐近上界与下界，资源估算把渐近结论变成可执行的工程预算。
量子复杂度与经典复杂度的关系，是理解全课的锚点。经典计算中，P 是多项式时间可解问题，NP 是多项式时间可验证问题，BPP 是随机多项式时间可解问题。量子计算中，BQP 对应“量子多项式时间可解”，它包含 BPP，且普遍认为不包含 NP 全部（除非多项式层级坍塌）。这意味着量子计算并非万能加速器：Shor 算法把整数分解从亚指数降到多项式，Grover 算法只把无序搜索从 O(N) 降到 O(√N)，而许多 NP 完全问题在量子模型下仍没有已知的多项式算法。理解“哪些问题能加速、加速到什么程度、代价是什么”，比记住几个算法名字重要得多。
资源估算之所以独立成章，是因为渐近复杂度会掩盖常数与工程现实。一个 O(N³) 的量子算法，若每个逻辑门需要上千个物理门和多次纠错周期，实际运行时间可能远超预期。资源估算通常沿两条线展开：逻辑层关注量子比特数、T 门数、CNOT 数、电路深度；物理层关注纠错码距离、码距与错误率关系、魔态蒸馏开销、物理量子比特总数与时钟周期。以表面码为例，若物理错误率 p 约为 10⁻³，码距 d 通常需取 15～25 才能把逻辑错误率压到 10⁻¹⁰ 量级，而每个逻辑量子比特对应 d² 量级的物理量子比特，再乘以魔态工厂与路由开销，最终物理比特数往往是逻辑比特数的数百到数千倍。这些数字不是装饰，而是判断“某算法能否在近期硬件上跑起来”的关键依据。
本课程的知识地图按“由抽象到具体、由理论到工程”组织，共 30 章，可划分为五个板块。第一板块是基础与全景（第 1～4 章）：建立复杂度与资源估算的定义、研究范畴、与经典复杂度的关系，并引入量子线路与通用门集。第二板块是复杂度理论核心（第 5～12 章）：系统讲解 BQP、QMA、量子查询复杂度、下界证明方法（多项式方法、对抗方法、张量积方法）以及量子随机存取机等模型。第三板块是算法与资源分析（第 13～20 章）：以 Shor、Grover、HHL、量子模拟、量子化学与优化算法为对象，逐一拆解其逻辑资源需求与加速边界。第四板块是纠错与物理资源估算（第 21～26 章）：从稳定子码、表面码到魔态蒸馏、晶格手术，建立从逻辑比特到物理比特的换算方法。第五板块是工程实践与前沿（第 27～30 章）：讨论编译与路由、资源估算工具链、近期硬件约束下的可行性评估，以及容错量子计算的发展路线。
学习路径上，建议按“先建立坐标系，再填充细节”的方式推进。第一步，掌握复杂度类之间的包含关系与已知分离结果，能判断一个问题大致落在哪个类中。第二步，学会阅读算法伪代码并提取其门级资源：识别受控门、T 门、辅助比特与测量操作。第三步，掌握至少一种纠错码的资源换算公式，例如表面码中逻辑错误率随码距的指数抑制关系，以及物理比特数与码距的平方关系。第四步，能使用资源估算工具或手算表格，对一个小规模实例（如 2048 位整数分解）给出量级估计，并说明假设条件。第五步，能对估算结果做敏感性分析：当物理错误率、门时间、蒸馏效率变化时，结论如何变化。
需要特别提醒的是，资源估算的结论高度依赖假设。同一算法在不同纠错码、不同连接拓扑、不同门错误率下，物理比特数可能相差一个数量级以上。因此，本课程中出现的所有具体数字，除非特别说明，均属于教学示例或基于公开文献的合理假设，用于演示估算方法，而非对某台真实机器的实测结论。学会标注假设、区分量级估计与精确计算，是资源估算能力的重要组成部分。
最后，本课程不要求你先成为量子物理专家，但要求你具备基本的线性代数、概率论与算法分析基础。若对量子门、叠加与纠缠还不熟悉，可在学习过程中随时回看第 2～4 章的基础内容。复杂度与资源估算的价值，在于它把“量子计算很快”这句口号，转化为可检验、可比较、可工程化的量化判断。掌握这套语言，你才能在面对一个新算法或一台新硬件时，独立回答“它到底能做什么、代价多大、是否值得”。