4. 量子近似优化算法（QAOA）求解调度问题
量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是面向组合优化问题的变分量子算法。它把调度问题编码成一个成本哈密顿量，再通过交替施加“成本演化”和“混合演化”两类酉操作构造参数化量子线路，最后用经典优化器调整线路参数，使测量得到的解质量逐步提升。理解 QAOA 求解调度问题，关键要抓住三件事：成本哈密顿量如何表达调度目标与约束、混合哈密顿量如何保证搜索空间不塌缩、参数与线路深度如何影响最终解的质量。
一、QAOA 算法框架
QAOA 的输入是一个组合优化问题，输出是一组近似最优的比特串。设问题变量用 n 个量子比特表示，成本哈密顿量 HC 对每个计算基态 |z⟩ 给出对应的目标函数值 C(z)。QAOA 构造深度为 p 的线路：
|ψ(β, γ)⟩ = e^{-iβ_p H_B} e^{-iγ_p H_C} … e^{-iβ_1 H_B} e^{-iγ_1 H_C} |+⟩^{⊗n}其中 HB 是混合哈密顿量，通常取 HB = Σi Xi，对应每个量子比特上的 X 旋转；γ 控制成本项的作用强度，β 控制混合项的作用强度。初始态 |+⟩⊗n 是所有计算基态的均匀叠加，保证搜索从整个可行空间出发。测量后得到比特串 z，其目标值 C(z) 的期望 ⟨HC⟩ 就是优化目标。经典优化器不断更新 (β, γ)，直到期望值收敛或达到迭代上限。
二、调度问题的成本哈密顿量设计
以“n 个作业分配到 m 台机器、最小化最大完工时间”的简化调度问题为例。用一组比特 xj,k 表示作业 j 是否分配到机器 k，每个作业恰好分配一次，即 Σk xj,k = 1。设作业 j 在机器 k 上的处理时间为 tj,k，则机器 k 的负载为 Lk = Σj tj,k xj,k，目标是最小化 maxk Lk。
把目标与约束写成哈密顿量时，常用“惩罚项 + 目标项”的结构：
H_C = A · Σ_j (Σ_k x_{j,k} - 1)^2 + B · Σ_k L_k^2第一项是分配约束惩罚，A 取足够大，使违反“每作业恰好分配一次”的比特串获得高能量而被压制；第二项用负载平方和近似“最大负载最小化”，因为平方和对大负载的惩罚更重，能引导解向均衡分配靠拢。需要注意，平方项展开后会出现比特之间的二次耦合，这正是 QAOA 线路中需要两比特门的原因。若问题规模较大，也可用辅助比特或分段线性化处理 max 目标，但会增加比特数与线路复杂度。
三、参数化量子线路设计
成本演化层 e−iγHC 的实现取决于 HC 的项结构。对单比特项 Zi，直接施加 RZ(2γ) 旋转；对两比特耦合项 ZiZj，先施加 CNOT，再在目标比特上施加 RZ(2γ)，再施加 CNOT 还原，这是标准的 ZZ 演化分解。混合层 e−iβHB 则对每个比特施加 RX(2β)。因此一层 QAOA 的线路由“RZ + 两比特 ZZ 演化”与“RX”交替组成，深度 p 层意味着这套结构重复 p 次。
四、参数优化策略
QAOA 的优化变量是 2p 个角度 (γ1,…,γp, β1,…,βp)。目标函数是测量得到的 ⟨HC⟩，它只能通过有限次采样估计，因此带有统计噪声。常用策略有三类：
- 无梯度方法：COBYLA、Nelder–Mead 等，适合采样噪声较大、参数维度不高的场景，实现简单，但收敛速度较慢。
- 梯度方法：利用参数移位规则精确计算 ∂⟨HC⟩/∂θ，每个参数只需两次额外线路评估，适合参数维度中等且线路可微的情形。
- 启发式初值：p 较小时，γ 与 β 存在近似线性或周期性规律，可先用小 p 优化得到参数，再插值作为大 p 的初值，减少陷入局部极小的概率。
实践中还要注意“采样数—优化轮数”的平衡：每次评估采样数太少，目标值噪声大，优化器容易误判方向；采样数太多，则总线路执行次数急剧上升。一个可操作的示例设置是：n=6 个作业、m=3 台机器、p=2，每轮评估采样 1024 次，优化器最多迭代 100 轮，学习率或步长从 0.1 起逐步衰减。这些数值属于教学示例，实际应结合硬件噪声与问题规模调整。
五、线路深度对解质量的影响
深度 p 是 QAOA 最重要的超参数之一。理论上 p 越大，线路可表达的态空间越大，近似比有望提高；但实际中 p 增大带来三个问题：参数维度增加使优化地形更复杂、更容易出现贫瘠高原；两比特门数量线性增长，在含噪设备上累积误差；单次线路执行时间变长，采样成本上升。因此常见做法是先在小 p 上验证成本哈密顿量编码是否正确、约束惩罚是否有效，再逐步增加 p 观察近似比是否仍有明显提升。若 p 从 1 增到 3 时目标值改善很小，而门数已接近设备可承受上限，就应优先考虑改进编码或换用其他求解路径，而不是继续加深线路。