1. 课程导入与QAOA全景

在组合优化问题中，我们常常面对这样一类任务：从数量随规模指数增长的可行解中，找出使某个目标函数最小（或最大）的那一个。经典算法如分支定界、动态规划、启发式搜索在规模较小时表现良好，但当变量数达到数十乃至上百、约束彼此耦合时，求解时间会迅速膨胀。量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）正是在这一背景下被提出的：它不承诺精确最优，而是利用量子线路的参数化结构，在多项式深度内构造一个近似解，并通过经典优化器调节参数，使测量结果的期望目标值逐步逼近最优。

QAOA 由 Farhi 等人在 2014 年提出，其核心思想可以概括为“问题哈密顿量 + 混合哈密顿量 + 交替演化”。把组合优化问题编码为伊辛型代价哈密顿量 H_C，其基态对应最优解；再引入混合哈密顿量 H_B（通常取所有量子比特上的 X 算符之和），用于在解空间中进行“翻转”探索。线路由 p 层交替的代价演化 e^{-iγH_C} 与混合演化 e^{-iβH_B} 构成，初始态取均匀叠加态 |+⟩^⊗n。参数 γ、β 由经典优化器迭代更新，最终对线路输出进行测量，取出现频率最高的比特串作为近似解。

上图把 QAOA 的完整工作流压缩为四个阶段与一个闭环：左侧是问题编码，中间是参数化线路，右侧是测量与经典优化，下方是结果判读。需要特别注意的是那条虚线反馈回路——QAOA 不是一次性执行的量子算法，而是“量子线路负责采样、经典优化器负责调参”的混合迭代过程。理解这一点，是后续所有建模与调优工作的前提。

QAOA 在组合优化中的定位

从算法谱系看，QAOA 属于变分量子算法（VQA）家族，与 VQE 共享“参数化线路 + 经典优化”的框架，区别在于 QAOA 的线路结构由问题哈密顿量直接决定，具有明确的组合优化语义。与量子退火相比，QAOA 是门模型下的离散时间演化，层数 p 可以显式控制；当 p→∞ 时，理论上可逼近绝热演化，从而收敛到最优解，但实际受限于线路深度与噪声，通常取较小的 p（如 1～5）来换取可执行性。与 Grover 搜索相比，QAOA 不追求二次加速的精确搜索，而是以较低线路深度获得有保证的近似比，更适合当前含噪声中等规模量子（NISQ）设备的约束。

在应用层面，QAOA 最自然的落点是 Max-Cut、图着色、旅行商、背包、投资组合优化、航班调度等 NP 难或 NP 完全问题。这些问题都可以写成二次无约束二值优化（QUBO）形式，再通过 Z_i → 1-2x_i 的替换转为伊辛模型。因此，掌握“问题 → QUBO → 伊辛 → 线路”的转换链条，是本课程的第一项硬技能。

本课程的学习路径与实战目标

课程共 30 章，整体按“基础—建模—实现—调优—评估”推进。前段建立 QAOA 的数学图像：代价哈密顿量、混合哈密顿量、参数化线路与近似比的定义；中段聚焦建模，把 Max-Cut、背包、旅行商等典型问题逐一转成 QUBO 与伊辛形式，并讨论约束罚项系数的选取；后段进入实现与调优，使用 Qiskit 或 PennyLane 搭建线路、选择优化器、处理测量采样与参数初始化，最后通过近似比、约束满足率、运行时间等指标与经典基线对比。

实战目标设定为：能够独立完成一个中等规模组合优化问题的端到端求解，包括问题建模、线路实现、参数优化、结果解码与质量评估，并能解释 p、罚项系数、测量次数、优化器选择对结果的影响。下面给出一个可直接参考的建模检查清单，用于在动手前快速核对关键输入是否齐备。