📚 课程目录第2章量子优化基础回顾

2. 量子优化基础回顾

在进入约束建模与罚项设计之前，需要先把“量子优化到底在优化什么”这件事对齐。无论底层硬件是量子退火器还是门模型量子计算机，绝大多数组合优化问题的求解流程都可以归结为三步：把业务问题写成带约束的优化形式，把约束与目标合并成一个二次型能量函数，再让量子硬件或量子—经典混合算法去寻找该能量函数的低能态。本节围绕这条主线，回顾量子退火与门模型两类求解范式，说明QUBO与Ising模型的形式与相互转换，并指出变量映射与约束处理中最容易踩坑的地方。

两类求解范式：退火与门模型

量子退火（Quantum Annealing）直接面向伊辛型能量函数。以D-Wave类设备为例，硬件求解的问题形如

E(s) = Σ_i h_i s_i + Σ_{i<j} J_ij s_i s_j,   s_i ∈ {−1, +1}

其中 h_i 是作用在第 i 个量子比特上的局部场，J_ij 是比特间的耦合强度。退火过程让系统从容易制备的初始哈密顿量缓慢演化到问题哈密顿量，理想情况下系统停留在全局低能态。它的优点是变量与耦合直接映射到硬件拓扑，缺点是硬件比特连接稀疏（ Chimera、Pegasus 等拓扑），且耦合系数精度有限。

门模型量子优化则走另一条路：把优化问题编码进一个量子态或量子线路，通过 QAOA、量子相位估计或 Grover 类算法求解。以 QAOA 为例，代价哈密顿量 H_C 对应目标函数，混合哈密顿量 H_B 驱动状态在解空间转移，线路由交替的 exp(−iγH_C) 与 exp(−iβH_B) 构成，参数 (γ, β) 由经典优化器迭代调整。门模型灵活但受限于线路深度与比特数，当前更适合中小规模问题或作为混合算法的子程序。

QUBO与Ising：同一枚硬币的两面

QUBO（Quadratic Unconstrained Binary Optimization）使用二进制变量 x_i ∈ {0,1}，目标形式为

f(x) = Σ_i Q_ii x_i + Σ_{i<j} Q_ij x_i x_j

它与Ising模型通过线性变换一一对应：令 s_i = 2x_i − 1，即 x_i = (1 + s_i)/2，代入后即可把 Q 矩阵转换为 h 与 J。反过来，s_i = 2x_i − 1 也成立。这个变换看似简单，却决定了两个实践细节：其一，常数项会平移能量，不影响最优解位置，但会影响罚项强度的相对比较；其二，QUBO 中 x_i x_i = x_i（因为 0²=0、1²=1），所以对角项 Q_ii 实际是线性项，写矩阵时不要重复计算。

举例说明转换。设 QUBO 为 f = 3x₁ + 2x₂ − 4x₁x₂。代入 x_i=(1+s_i)/2：

3x₁ = 1.5 + 1.5s₁
2x₂ = 1.0 + 1.0s₂
−4x₁x₂ = −4·(1+s₁)(1+s₂)/4 = −1 − s₁ − s₂ − s₁s₂
合并：f = 1.5 + (1.5−1)s₁ + (1.0−1)s₂ − s₁s₂
     = 1.5 + 0.5s₁ + 0s₂ − 1·s₁s₂

于是 h₁=0.5、h₂=0、J₁₂=−1，常数 1.5 可丢弃。验证：x=(1,1) 即 s=(+1,+1)，原式 f=3+2−4=1；Ising 式 0.5+0−1=−0.5，加回常数 1.5 得 1，一致。这类手算转换在调试映射代码时非常有用。

变量映射与目标函数构建

实际建模时，业务变量往往不是二值的：选址有“选/不选”，排班有“员工 i 上 shift j”，路径有“边 (u,v) 是否被经过”。标准做法是引入指示变量 x_{i,j} ∈ {0,1}，再用线性或二次表达式写出目标。例如带权集合覆盖：给定元素集合 U、候选集合 S_k 及其代价 c_k，目标是最小化总代价并覆盖所有元素，可写为

min  Σ_k c_k x_k
s.t. Σ_{k: e∈S_k} x_k ≥ 1,  ∀e ∈ U
     x_k ∈ {0,1}

目标函数本身是线性的，直接进入 Q 的对角线；约束则需要通过罚项并入目标。这里的关键判断是：目标函数决定“好坏”，约束决定“可行”，两者在 QUBO 中被压进同一个标量，因此量纲与权重的相对大小必须仔细设计，这正是下一节罚项设计的核心议题。

约束处理的基本挑战

QUBO 与Ising在形式上都是无约束的，所有约束必须转化为罚项。以等式约束 Σ_i x_i = 1（恰好选一个）为例，常用罚项为 P(Σ_i x_i − 1)²，展开后产生线性项与二次项，P 为罚项系数。展开时要注意：平方项 x_i² 退化为 x_i，交叉项 2x_i x_j 的系数要正确写入 Q_ij（QUBO 通常约定 i<j 时只存一份，若矩阵对称存储则需除以 2）。

实践中的主要挑战有四类。第一，罚项强度：P 太小，不可行解可能比可行解能量更低；P 太大，能量景观被罚项主导，退火或 QAOA 难以找到好解，且受硬件耦合精度限制可能被截断。第二，量纲不一致：目标代价可能是百量级，约束违反计数是个位数，直接相加会让约束形同虚设，通常需要先归一化或按最大可能违反量缩放。第三，变量数膨胀：不等式约束 Σx ≥ 1 需要引入松弛变量转为等式，每个松弛变量都占用比特，在稀疏拓扑上还要额外链式连接。第四，不可行解的解码：硬件返回的低能态未必满足约束，需要后处理修复或拒绝，这会直接影响有效采样率。

一个实用的检查习惯：把候选解代回原始约束逐条校验，统计“可行解比例”和“可行解中的最优值”，而不是只看硬件报告的最低能量。最低能量若来自不可行解，说明罚项强度或建模本身需要调整。

小结本节要点：退火与门模型是两条实现路径，但共享同一个数学内核——二次型能量函数；QUBO 与Ising通过 s=2x−1 互相转换，转换时注意常数项与对角项；变量映射要把业务语义准确落到 0/1 指示变量上；约束必须靠罚项进入目标，而罚项强度、量纲、变量膨胀与解码校验构成了约束处理的基本挑战。把这些基础打牢，后续的罚项设计与调参才有可靠的出发点。