当前位置：首页 > news >正文

量子退火实战：从“背包问题”到QUBO建模的完整思考过程

news 2026/7/16 4:19:21

量子退火实战：从“背包问题”到QUBO建模的完整思考过程

量子计算正在从实验室走向实际应用，而量子退火作为解决组合优化问题的利器，吸引了越来越多算法爱好者的目光。但面对一个具体问题时，如何将其转化为量子退火能够处理的QUBO形式，往往成为第一道门槛。本文将以经典的0/1背包问题为例，带你走完从问题定义到QUBO建模的全过程，重点培养"将实际问题数学化"的思维能力。

1. 问题定义与变量设计

背包问题描述很简单：给定一组物品，每个物品有重量和价值，在背包承重限制下，如何选择物品使总价值最大。但要将这个日常描述转化为数学模型，需要解决几个关键问题：

决策变量：如何用数学表达"选或不选"？
目标函数：如何量化"总价值最大"？
约束条件：如何表示"重量不超过限制"？

在量子退火框架下，我们通常采用二进制变量：

x_i = 1 # 选择第i个物品 x_i = 0 # 不选择第i个物品

假设有N个物品，背包承重为W，第i个物品重量为w_i，价值为v_i。目标函数可以直观地表示为：

最大化：Σ(v_i * x_i) (i从1到N)

但这还不是QUBO需要的形式——我们需要的是最小化问题。简单的转换方法是取负值：

最小化：-Σ(v_i * x_i)

提示：量子退火总是寻找使哈密顿量最小的解，因此所有优化问题都需要转化为最小化形式

2. 约束条件的惩罚函数设计

背包问题的核心约束是总重量不超过W。用数学表达就是：

Σ(w_i * x_i) ≤ W

在QUBO建模中，约束条件需要通过惩罚函数融入目标函数。基本思路是：当违反约束时，给目标函数加上一个很大的"惩罚"，使解变得不优。具体实现方式：

将不等式改写为等式形式：
```
Σ(w_i * x_i) + s = W
```
其中s是松弛变量，表示"剩余容量"
构造惩罚项：
```
P = λ*(Σ(w_i * x_i) + s - W)^2
```
λ是惩罚系数，需要足够大以确保约束被满足

将惩罚项加入原目标函数：

H = -Σ(v_i * x_i) + λ*(Σ(w_i * x_i) + s - W)^2

实际应用中，松弛变量s的处理有多种选择：

松弛变量类型	表达式	适用场景
二进制编码	s = Σ(2^k * y_k)	精确控制松弛量
单一变量	s = y	快速实现，精度较低

3. 完整QUBO矩阵构建

现在我们将所有部分组合起来，构建完整的QUBO表达式。以一个具体例子说明：

假设有3个物品：

重量w = [2, 3, 4]
价值v = [5, 7, 9]
背包容量W = 5

选择二进制编码松弛变量s = y1 + 2*y2（因为最大可能超重是2+3+4-5=4）

完整哈密顿量：

H = -5x1 -7x2 -9x3 + λ(2x1 +3x2 +4x3 +y1 +2y2 -5)^2

展开平方项后，我们可以得到各项系数，整理成QUBO矩阵形式。使用PyQUBO库可以自动完成这个过程：

from pyqubo import Binary, Constraint # 定义变量 x1, x2, x3 = Binary('x1'), Binary('x2'), Binary('x3') y1, y2 = Binary('y1'), Binary('y2') # 惩罚系数 M = 10.0 # 哈密顿量 H = -5*x1 -7*x2 -9*x3 + M*Constraint((2*x1 +3*x2 +4*x3 +y1 +2*y2 -5)**2, label='weight_constraint') # 编译为QUBO model = H.compile() qubo, offset = model.to_qubo()

得到的QUBO矩阵可以直接输入量子退火器求解。