4. 量子优化与QUBO建模
要把0-1背包问题交给量子优化器（如量子退火机、QAOA线路或Ising求解器）处理，第一步不是写量子门，而是把问题改写成这些硬件能够“读懂”的数学形式。QUBO（Quadratic Unconstrained Binary Optimization，二次无约束二值优化）正是最通用的桥梁：它只允许二值变量、只允许一次项和二次项、并且不允许显式约束。背包问题天然带有“总重量不超过容量”的约束，因此建模的核心工作就是——把约束“折叠”进目标函数，用惩罚项代替约束。
一、QUBO的标准形式与符号约定
QUBO的标准写法为：
minimize E(x) = Σ_i Q_ii · x_i + Σ_{i<j} Q_ij · x_i · x_j , x_i ∈ {0,1}其中 Q 是一个上三角（或对称）实矩阵，Q_ii 是变量 x_i 的一次项系数（线性偏置），Q_ij 是变量对之间的耦合系数。约定全文统一：求解方向为最小化，若原问题是最大化收益，则对目标整体取负号。这一点必须在建模开始就固定，否则后续惩罚项的正负号会全部错乱。
QUBO与Ising模型可以互相转换：令 x_i = (1 + s_i)/2，s_i ∈ {-1,+1}，即可得到 Σ h_i s_i + Σ J_ij s_i s_j 的形式。多数量子退火SDK（如D-Wave Ocean）内部以Ising求解，但对外提供QUBO接口，因此我们只需专注QUBO矩阵的构造。
二、把背包目标写成二次型
设共有 n 件物品，物品 i 的价值为 v_i、重量为 w_i，背包容量为 W，决策变量 x_i ∈ {0,1} 表示是否装入。原始问题是：
maximize Σ_i v_i · x_i
subject to Σ_i w_i · x_i ≤ W由于QUBO只含一次与二次项，而目标 Σ v_i x_i 本身就是线性的，直接映射为 Q_ii = -v_i（取负以转为最小化）即可，无需引入任何辅助变量。真正棘手的是容量约束。
三、约束处理：惩罚项设计
QUBO处理不等式约束的通用手段是“罚函数法”：构造一个违反约束时为正、满足约束时为零（或极小）的惩罚函数 P(x)，乘以足够大的惩罚系数 λ，加到目标上：
E(x) = -Σ_i v_i x_i + λ · P(x)对背包的容量约束 Σ w_i x_i ≤ W，常用做法是引入松弛变量把不等式变成等式。令松弛量 s = W - Σ w_i x_i ≥ 0，用二进制展开表示 s = Σ_{k} 2^k · y_k（y_k ∈ {0,1}，展开位数 m = ⌈log2(W+1)⌉），则惩罚项为：
P(x) = ( Σ_i w_i x_i + Σ_k 2^k y_k - W )²当且仅当所选物品总重恰好等于 W - s（即不超重）时，P(x)=0。展开这个平方，会自然产生 x_i·x_j、x_i·y_k、y_k·y_l 三类二次交叉项，正好落入QUBO的二次型框架。这就是“二次”二字的来源——平方惩罚天然生成耦合。
λ 的选取原则：λ 必须大于“任意可行解与任意不可行解之间的目标差”，才能保证最优解一定落在可行域内。经验上取 λ > max(v_i) 或 λ ≈ 1.5 × Σ v_i 是安全起点，但过大的 λ 会压缩能量尺度、加剧量子退火的精度问题，需要在可行性与数值稳定性之间权衡。四、一个可手算的建模示例
取4件物品，容量 W = 10：
| 物品 i | 价值 v_i | 重量 w_i |
|---|---|---|
| 0 | 6 | 5 |
| 1 | 5 | 4 |
| 2 | 4 | 3 |
| 3 | 3 | 2 |
松弛变量位数 m = ⌈log2(11)⌉ = 4，即 y_0,y_1,y_2,y_3 对应权 1,2,4,8。惩罚项为 (5x_0+4x_1+3x_2+2x_3 + y_0+2y_1+4y_2+8y_3 - 10)²。取 λ = 10，则总能量：
E(x,y) = -(6x_0+5x_1+4x_2+3x_3) + 10·(5x_0+4x_1+3x_2+2x_3+y_0+2y_1+4y_2+8y_3-10)²验证一个候选解：装物品0和1，总重9、总价值11，松弛量 s=1，取 y_0=1 其余为0。此时括号内 9+1-10=0，惩罚为0，能量 E = -11。再试装物品0、1、2，总重12超重，括号内 12-10=2，惩罚 10×4=40，能量 E = -15+40 = 25，远高于可行解，被正确“罚掉”。这说明只要 λ 足够大，能量最低点必然对应可行且收益高的组合。
五、建模中的常见陷阱与工程建议
其一，惩罚系数不是越大越好。量子退火的有效能量分辨率有限，若 λ 取到 10⁴ 量级，而目标项只有个位数，则目标差异会被数值噪声淹没，退火过程无法区分“好可行解”和“差可行解”。建议先按 λ = 1.2 × (Σv_i + 1) 估算，再根据实际求解质量微调。
其二，松弛变量的位数要精确。若 W = 10，m = 4 位可表示 0～15，覆盖了所有可能的松弛量；若误取 m = 3（最大7），则松弛量 8、9、10 无法表示，会人为排除掉“几乎装满”的优质解。位数公式 m = ⌈log2(W+1)⌉ 必须严格执行。
其三，变量规模与耦合密度。松弛变量会额外引入 m 个变量，且平方展开后 x_i 与 y_k 之间产生 n×m 个耦合项。对 n=100、W=1000 的实例，变量数约 110，耦合项可达数千，已接近当前量子退火机的连接度上限，通常需要先做问题分解或次嵌入（minor embedding）。
Q 时建议同时维护一张“索引 → 物理含义（物品i / 松弛位k）”的映射表，否则在解读最优解 x* 时极易把松弛位误读为物品决策位。