1. 课程导入与QAOA全景
组合优化问题广泛存在于排班、路由、投资组合、芯片布线与物流调度中。它们的共同特征是：决策变量离散、约束条件多、可行解数量随规模指数增长。经典精确算法在小规模下可以得到最优解，但一旦变量数上升到几十甚至上百，求解时间往往不可接受。量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）正是在这一背景下提出的：它把组合优化问题编码为伊辛模型或量子哈密顿量，用浅层参数化量子线路生成候选解，再通过经典优化器调节线路参数，使测量结果逐步逼近最优解。
本课程的目标不是停留在概念介绍，而是让学习者能够独立完成“问题建模—量子线路构造—参数优化—结果解读”的完整链路。学完本课程后，你应当能够：把一类组合优化问题写成二次无约束二值优化（QUBO）形式；将QUBO映射为伊辛哈密顿量并构造QAOA线路；理解p层QAOA中γ、β参数的作用；使用Qiskit或PennyLane搭建并运行小规模QAOA；通过采样结果评估近似比与成功率；并知道在什么规模、什么噪声条件下QAOA仍值得尝试。
整体技术路线
QAOA的求解流程可以概括为一条“经典—量子混合”闭环。左侧是经典侧：原始问题经过变量定义、约束惩罚、目标函数整理，形成QUBO矩阵；再通过变量替换x=(1−z)/2转为伊辛模型，得到代价哈密顿量H_C。右侧是量子侧：以均匀叠加态|+⟩^⊗n为初态，交替施加代价演化e^{−iγH_C}与混合演化e^{−iβH_B}，重复p次后测量。测量得到的比特串返回经典优化器，计算期望能量⟨H_C⟩，优化器更新γ、β，再送回量子线路。循环直到期望能量收敛或达到迭代上限。
关键概念与参数
理解QAOA需要抓住三个核心对象。第一是代价哈密顿量H_C，它把目标函数编码为对角算符，其本征值对应各比特串的目标函数值。第二是混合哈密顿量H_B，通常取H_B=∑X_i，作用是让量子态在不同计算基态之间转移，避免陷入局部最优。第三是层数p，它决定线路深度与表达能力：p=1时只能捕捉非常有限的关联，p增大后近似比通常提升，但线路深度和噪声影响也随之增加。
参数γ和β各有明确角色。γ控制代价演化的强度，相当于在解空间中“偏向”低能量区域的力度；β控制混合演化的强度，相当于“探索”其他候选解的幅度。二者交替作用，使量子态在“利用已知好解”和“探索新解”之间取得平衡。对于MaxCut问题，p=1时QAOA的近似比约为0.6924；p增大后逐步逼近1，但收敛速度与问题结构密切相关。
工具链准备
本课程使用Python生态。推荐环境为Python 3.10以上，核心依赖包括：Qiskit（量子线路构建与模拟）、Qiskit Optimization（QUBO与伊辛转换）、PennyLane（可选，用于自动微分与梯度优化）、NumPy与SciPy（数值计算与经典优化）、Matplotlib（结果可视化）。安装命令如下：
pip install qiskit qiskit-optimization qiskit-aer
pip install pennylane numpy scipy matplotlib验证环境是否可用，可运行一段最小示例：构造2比特MaxCut的QUBO，转为伊辛模型，用Qiskit的QAOA求解并打印最优比特串与近似比。若输出中包含类似“optimal bitstring: 01”与“approximation ratio: 0.85”的信息，说明工具链已就绪。注意：这里的数值属于示例性结果，实际运行会因随机种子、优化器与层数不同而变化。