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

在进入 QAOA 的量子线路与参数优化之前，必须先回答一个更基础的问题：一个现实中的组合优化问题，如何被写成量子算法能够处理的数学形式？这一节围绕四个层次展开——决策变量、目标函数、约束条件，以及从图论表示到 Ising 模型的转换。理解这条链路，才能明白 QAOA 的哈密顿量究竟从何而来。

一、决策变量：把"选择"变成可计算的符号

组合优化的本质是在有限个离散方案中挑出最优的一个。建模的第一步，是把"选什么"翻译成变量。最常用的是 0-1 决策变量：x_i ∈ {0,1}，取 1 表示选中第 i 个对象，取 0 表示不选。例如背包问题中，x_i=1 表示把第 i 件物品放入背包；最大割问题中，x_i=1 表示顶点 i 被分到集合 A，取 0 则分到集合 B。

有些问题需要整数变量，如 x_i ∈ {0,1,2,...} 表示分配的数量；也有问题用 ±1 变量 s_i ∈ {-1,+1}，这在物理和 Ising 模型中更自然。0-1 变量与 ±1 变量之间存在确定的换算关系：s_i = 1 - 2x_i，即 x_i=0 ↔ s_i=+1，x_i=1 ↔ s_i=-1。这个换算关系在后续 Ising 转换中会反复用到，务必记牢方向。

二、目标函数与约束条件：定义"好"与"可行"

目标函数刻画方案的好坏，通常写成变量的线性或二次表达式。以最大化问题为例，背包问题的目标是最大化总价值 Σ v_i x_i；最大割问题的目标是最大化被割断的边数，这是一个关于变量的二次函数。约束条件则限定哪些方案是可行的，例如背包的容量约束 Σ w_i x_i ≤ C，或最大割中"每个顶点必须且只能属于一个集合"的隐含约束。

这里有一个关键区分：硬约束必须严格满足，违反即不可行；软约束允许违反，但要在目标中付出惩罚代价。QAOA 处理约束的主流思路，是把硬约束通过惩罚项并入目标函数，转化为无约束优化。例如容量约束可写成惩罚项 P·max(0, Σ w_i x_i - C)²，其中 P 是足够大的惩罚系数。P 的选取很讲究：太小则不可行解仍可能被选中，太大则能量尺度悬殊、影响优化稳定性。

三、图论表示：组合问题的通用语言

大量组合优化问题可以统一表示为图 G=(V,E) 上的问题，顶点集 V 对应决策对象，边集 E 对应对象之间的关联或冲突。这种表示的价值在于：它把问题的结构（谁和谁相关）与问题的数值（权重、收益）分离，而 QAOA 的量子线路结构恰恰由图的连接关系决定。

常见对应关系包括：最大割在无向图上定义，目标是让割断边的权重之和最大；最大独立集要求选出的顶点两两不相邻；旅行商问题则在完全图上寻找最小权重的哈密顿回路。以最大割为例，若图有 4 个顶点、边为 (1,2)、(2,3)、(3,4)、(4,1)，权重均为 1，则把 {1,3} 与 {2,4} 分开可割断全部 4 条边，是最优解。这个简单例子可以直接用来验证后续转换是否正确。

四、从图问题到 Ising 模型：二次无约束二值优化

QAOA 的标准输入是 Ising 型哈密顿量，其一般形式为：

H = Σ_i h_i s_i + Σ_{i<j} J_ij s_i s_j,   s_i ∈ {-1,+1}

其中 h_i 是局部场系数，J_ij 是耦合系数。转换的目标，就是把组合优化问题写成这个形式（通常还要最小化）。转换分三步走：

1. 写出 0-1 形式的目标函数，包含原始目标和惩罚项，统一为最小化（最大化取负号）。
2. 变量替换：用 x_i = (1 - s_i)/2 代入，把 0-1 变量换成 ±1 变量。
3. 展开并整理：合并同类项，得到 h_i 与 J_ij。常数项不影响最优解位置，可暂时忽略。

以最大割为例，目标是最小化 -Σ_{(i,j)∈E} w_ij (x_i + x_j - 2x_i x_j)。代入替换式并整理，可得 J_ij = w_ij/2（对每条边），而局部场 h_i 与顶点度数相关。这说明：图的每条边对应一个耦合项 J_ij，图的拓扑直接决定量子线路中两比特门的连接方式。这正是图论表示与量子实现之间的桥梁。

五、转换流程的可视化

下图把本节的核心链路串起来：从现实问题出发，经决策变量、目标与约束、图论表示，最终落到 Ising 模型的 h_i 与 J_ij，并标注了每一步的关键操作与易错点。

六、建模检查清单

完成一次建模后，建议按以下要点自查，避免把错误带入 QAOA 求解阶段：

其中"小规模验证"尤其重要。对于 n ≤ 10 的问题，可以穷举所有 2^n 个 ±1 赋值，计算 Ising 能量，确认最低能量对应的解与原始问题的最优解一致。这一步能在几分钟内发现绝大多数建模错误，是进入 QAOA 线路设计前性价比最高的检查。