4. 问题到QUBO的转化方法

把实际优化问题交给量子退火器之前，必须先把它写成QUBO（二次无约束二值优化）形式。QUBO的标准形式是

minimize  E(x) = Σ_i Q_ii x_i + Σ_{i<j} Q_ij x_i x_j ,  x_i ∈ {0,1}

其中对角项 Q_ii 表示线性系数，非对角项 Q_ij 表示变量之间的耦合。注意QUBO本身是“无约束”的，所有约束都必须被吸收进目标函数。因此转化的核心工作可以概括为三件事：变量编码（把决策量映射成0/1比特）、约束处理与惩罚项设计（把约束变成能量代价）、系数调节（让惩罚足够强又不淹没目标）。

一、变量编码：把决策量变成比特

最直接的是二值变量，例如“是否选择第 i 个物品”用 x_i∈{0,1} 表示。当决策量是整数或连续量时，需要编码成一组比特。常见方式有三种：

• 二进制编码：整数 n 用 Σ 2^k x_k 表示，比特数少，但相邻数值的汉明距离可能很大，且表示范围是离散的。
• 独热编码（one-hot）：用 m 个比特中恰好一个为1来表示“取第 k 个值”，天然适合“从若干选项中选一个”的问题，约束形式简单，但比特数随选项数线性增长。
• 域墙编码（domain-wall）：用一串1后接一串0表示整数，相邻值只差一个比特翻转，适合需要平滑表示整数的场景。

编码方式直接决定后续约束的写法。例如用独热编码表示“每个任务只能分配给一台机器”，约束就是“每个任务的比特组内和为1”；若改用二进制编码，同样的约束会变成复杂的等式，惩罚项也更难设计。因此编码不是独立步骤，而是与约束处理一起考虑的。

二、约束处理与惩罚项设计

约束分等式与不等式两类。基本思路是：把“违反约束的程度”乘以一个惩罚系数，加到目标函数上，使可行解的能量低于任何不可行解。

等式约束：如 Σ_i x_i = 1（恰好选一个）。惩罚项写成 P(Σ_i x_i − 1)^2。展开后会出现平方项 x_i^2，而 x_i^2 = x_i（因为 x_i∈{0,1}），所以平方项可以化简为线性项，交叉项 x_i x_j 保留为耦合项。这是QUBO化简中最常用的恒等式。

不等式约束：如 Σ_i x_i ≤ k。需要引入松弛变量，把不等式变成等式：Σ_i x_i + s = k，其中 s 用若干比特表示 0 到 k 的整数。松弛变量同样要编码，并参与惩罚项。若 k 较小，也可用“超出即惩罚”的近似方式，但会损失精确性。

惩罚系数 P 的选取是关键。P 太小，退火器可能选择违反约束但目标更低的解；P 太大，会把整个能量面压得过于陡峭，导致目标函数的细微差异被数值精度淹没。一个常用的经验下界是：P 应大于“违反一次约束所能带来的最大目标收益”。例如目标系数绝对值最大为 W，则取 P > W 通常能保证可行解优先。

三、系数调节策略

QUBO矩阵的系数范围会直接影响量子退火器的物理实现。D-Wave等设备对耦合系数和局部场的动态范围有限制，通常需要把 Q 矩阵归一化到某个区间（如 [−1, 1] 或设备允许的 [−2, 2]）。归一化时若简单除以最大绝对值，可能使小系数被量化误差吞掉。因此常用策略是：

• 分层缩放：目标项与惩罚项分别缩放，保持惩罚项相对目标项的比值不变。
• 系数截断：把绝对值小于阈值的耦合置零，减少图连接密度，便于嵌入硬件拓扑。
• 链权重调节：嵌入时一个逻辑变量可能由多个物理比特链表示，链权重需足够大以保证链内比特一致，但过大会引入偏差。

下面这张图概括了从原始问题到QUBO、再到退火器可执行形式的完整转化链路，以及各环节的关键参数与判断点。

四、一个完整的转化示例

考虑一个简单的“三选一”问题：从三个候选方案中选一个，使成本最小，成本分别为 c₁=3, c₂=5, c₃=4。用独热编码 x₁,x₂,x₃∈{0,1}，约束为 x₁+x₂+x₃=1。

目标项：3x₁+5x₂+4x₃。惩罚项：P(x₁+x₂+x₃−1)²。展开惩罚项：

(x₁+x₂+x₃−1)²
= x₁²+x₂²+x₃² + 2x₁x₂+2x₁x₃+2x₂x₃ − 2x₁−2x₂−2x₃ + 1
= (x₁+x₂+x₃) + 2(x₁x₂+x₁x₃+x₂x₃) − 2(x₁+x₂+x₃) + 1
= 2(x₁x₂+x₁x₃+x₂x₃) − (x₁+x₂+x₃) + 1

取 P=10，合并后QUBO的对角项为：Q₁₁=3−10=−7，Q₂₂=5−10=−5，Q₃₃=4−10=−6；耦合项为 Q₁₂=Q₁₃=Q₂₃=20。常数项 10 不影响最优解，可忽略。此时检查三个可行解：

可见可行解能量均低于不可行解，最低能量对应 (1,0,0)，即选择方案一，符合预期。若把 P 降到 2，则 (0,0,0) 的能量为 2，低于 (1,0,0) 的 3，退火器就会返回不可行解——这正是惩罚系数过小的典型失败模式。

五、常见陷阱与排查

• 惩罚系数不足：表现为返回解违反约束。排查方法是手动计算几个不可行解的能量，确认它们都高于最优可行解。
• 系数动态范围过大：目标系数与惩罚系数相差几个数量级时，小系数在硬件上被量化掉。应做分层缩放并检查缩放后比值。
• 编码冗余：独热编码比特数多，嵌入后链长增加，链断裂概率上升。可考虑二进制或域墙编码减少比特数。
• 松弛变量范围估计错误：不等式约束的松弛变量上界必须覆盖实际可能的最大超出量，否则可行域被截断。

总结来说，问题到QUBO的转化是一个“编码—约束—调参—验证”的闭环。编码决定变量空间，惩罚项决定可行域，系数调节决定硬件可执行性，而验证决定整个转化是否可信。四者缺一不可，且往往需要反复迭代才能得到既正确又适合退火器执行的QUBO模型。