2. 组合优化问题建模基础

QAOA 并不是直接“吃”一个业务问题，它只认一种输入形式——伊辛模型（Ising Model）或等价的 QUBO（二次无约束二值优化）。因此，把实际问题转化为组合优化模型，再映射为伊辛哈密顿量，是使用 QAOA 求解的必经之路。本节以最大割（Max-Cut）和最小顶点覆盖（Min Vertex Cover）为例，完整走通这条建模链路，并说明每一步中容易出错的符号与常数约定。

一、建模链路：从问题到伊辛模型的三次转换

整个建模过程可以拆成三个明确的阶段。第一阶段是问题形式化：确定决策变量、约束条件和目标函数，得到一个标准的组合优化表述。第二阶段是约束消解：把约束通过罚函数（penalty）并入目标，得到无约束的 QUBO 形式。第三阶段是变量替换：把二值变量 x∈{0,1} 替换为自旋变量 s∈{−1,+1}，得到伊辛哈密顿量。QAOA 的线路参数化正是建立在这个哈密顿量之上。

二、最大割：目标函数如何写成二次型

给定无向图 G=(V,E)，最大割要求把顶点分成两个集合，使跨越两个集合的边数最多。定义 xᵢ=1 表示顶点 i 属于集合 A，xᵢ=0 表示属于集合 B。一条边 (i,j) 被割断，当且仅当 xᵢ≠xⱼ，用异或表示即 xᵢ+xⱼ−2xᵢxⱼ。于是目标函数为：

C(x) = Σ_{(i,j)∈E} (xᵢ + xⱼ − 2xᵢxⱼ)

这是一个纯二次多项式，没有约束，天然就是 QUBO 形式。注意 QAOA 的惯例是最小化哈密顿量，所以实际送入线路的是 −C(x)。若图有 m 条边，则 −C 的常数项与线性项在变量替换后会产生一个整体偏移，这个偏移不影响最优解的位置，但会影响能量期望值的读数，做结果比对时必须把它算进去。

以三角形图（3 个顶点、3 条边）为例，按上式展开并代入 xᵢ=(1−sᵢ)/2，得到 H=0.75+0.25(s₁s₂+s₂s₃+s₁s₃)。三个自旋全同号时 H=0.75+0.75=1.5，对应割边数 0；一正两负时 H=0.75−0.25=0.5，对应割边数 2。能量越低割边越多，与最小化约定一致。

三、最小顶点覆盖：约束如何变成罚项

最小顶点覆盖要求选出一个顶点子集，使每条边至少有一个端点被选中，且子集规模最小。令 xᵢ=1 表示选中顶点 i，目标是最小化 Σxᵢ，约束是每条边 (i,j) 满足 xᵢ+xⱼ≥1。约束不能直接进入伊辛模型，需要转成罚项：当 xᵢ=xⱼ=0 时约束被违反，罚项 (1−xᵢ)(1−xⱼ) 恰好取 1，否则取 0。于是：

H(x) = Σᵢ xᵢ + λ · Σ_{(i,j)∈E} (1 − xᵢ)(1 − xⱼ)

罚系数 λ 的选取是建模中最容易出错的地方。它必须大到让任何违反约束的解的能量都高于任何可行解。对本问题，一个可行解与最差违反解的目标差最多为 n（顶点数），因此取 λ>n 即可保证约束优先。λ 过小会得到“覆盖不全但规模很小”的伪最优解；λ 过大则会让能量尺度失衡，在 QAOA 中表现为目标项被罚项淹没，优化器难以分辨可行解之间的优劣。实践中常取 λ=n+1 或略大，并在结果分析时单独检查约束满足率。

四、变量替换与系数整理

把 xᵢ=(1−sᵢ)/2 代入 QUBO 后，需要把同类项合并，整理成 H=ΣJᵢⱼsᵢsⱼ+Σhᵢsᵢ+const 的标准形式。手工推导容易在符号和 1/2 因子上出错，建议固定一套流程：先展开所有乘积，再按 sᵢsⱼ、sᵢ、常数三类归并，最后用两三个随机自旋赋值回代验证。例如对上面的 MVC 罚项，展开 (1−xᵢ)(1−xⱼ) 后会出现 xᵢxⱼ 项，替换时产生 +J 型耦合，而线性项则来自目标函数与罚项展开的叠加，符号往往相反，必须逐项核对。

五、一个可复用的建模记录表

为了让建模过程可复查、可交接，建议对每个问题保留一份结构化记录。下表以三角形图 Max-Cut 为例填写，字段直接对应后续 QAOA 线路所需的输入。

完成上述步骤后，问题已经变成 QAOA 可以直接处理的伊辛形式：n 个量子比特对应 n 个自旋，耦合系数 Jᵢⱼ 决定 ZZ 相互作用的角度，局部场 hᵢ 决定单比特旋转的角度。后续只需按系数构造代价层与混合层，即可开始参数优化。需要强调的是，建模阶段的符号约定一旦确定，就要在系数表、线路实现和结果解读中全程保持一致，否则很容易出现“能量下降但原始目标变差”的假象。