1. 背包问题：从经典难题到量子求解的跨越

想象一下，你正准备进行一次长途旅行，面对琳琅满目的行李，你的背包容量有限。每件物品都有其重量和价值，比如沉重的专业相机能拍出大片，轻便的雨衣能应对天气变化。你的目标很简单：在背包承重范围内，选出总价值最高的物品组合。这个看似简单的“打包”问题，就是计算机科学和运筹学中著名的 背包问题 。它绝不仅仅是旅行前的烦恼，更是金融投资组合优化、资源分配、项目选择乃至芯片设计等众多核心领域的抽象模型。问题的难点在于，随着可选物品数量的增加，可能的组合方案会呈爆炸式增长。用传统计算机的“蛮力”方法逐一尝试所有组合，对于几十件物品可能就需要数年甚至更长时间，这在实际应用中是完全不可行的。

这正是 NP-Complete 问题的典型特征：验证一个方案是否最优相对容易，但要从海量可能性中找到那个最优方案却极其困难。长期以来，人们发展出动态规划、分支定界、启发式算法等多种方法来“近似”求解，在可接受的时间内得到一个“还不错”的解。然而，对于金融高频交易、物流全局调度、新药分子筛选等对最优解有极致追求的场景，近似解带来的潜在损失或效率折扣是难以接受的。近年来，一种新的计算范式—— 量子计算 ，特别是专注于解决组合优化问题的 相干光量子计算 技术路径，为解决此类难题带来了全新的思路。北京玻色量子科技有限公司发布的“天工量子大脑”，其核心目标之一，就是快速求解与背包问题同属一类难度的 Ising模型 。本文将深入拆解如何将背包问题精准映射为Ising/QUBO模型，并探讨这种新计算范式背后的原理与潜力。

2. 问题本质与建模思路解析

2.1 二次背包问题的精确定义

我们从一个更一般化也更复杂的变体—— 二次背包问题 入手。它与经典背包问题的核心区别在于，物品的价值不再是独立的。换句话说，选择物品A的价值，可能会因为是否同时选择了物品B而改变。这种“协同”或“拮抗”效应在现实中非常普遍。

例如，在投资组合中，持有股票A和股票B可能由于行业关联性而产生风险对冲或叠加效应，其组合价值并非两者简单相加。在广告投放中，在平台X和平台Y同时投放广告可能产生协同营销效果，总收益高于分别投放之和。在货物装载中，某些化学品不能混装（负协同），而某些商品组合运输能节省成本（正协同）。

其数学模型可以表述为一个 混合整数二次规划 问题：

最大化： Σᵢ Σⱼ vᵢⱼ xᵢ xⱼ + Σᵢ cᵢ xᵢ 约束条件： Σᵢ aᵢ xᵢ ≤ b 其中： xᵢ ∈ {0, 1}，表示是否选择物品i（1为选，0为不选）。 vᵢⱼ 表示物品i和j之间的交互价值（当i=j时，vᵢᵢ可视为物品i的独立价值cᵢ）。 aᵢ 是物品i的重量或资源消耗。 b 是背包的总容量或资源上限。

注意： 这个模型之所以是“二次”的，是因为目标函数中包含了xᵢxⱼ项，它刻画了变量之间的两两相互作用。这正是它能被映射到Ising模型（其能量函数也是自旋变量间的两两相互作用）的关键。

2.2 从约束优化到无约束QUBO模型

经典优化算法处理带约束的问题（如Σ aᵢ xᵢ ≤ b）通常比较复杂。而像“天工量子大脑”这类专攻Ising模型的量子计算设备，其天然适合求解的是 无约束 的二次优化问题。因此，我们需要一个巧妙的“翻译”过程，将约束条件转化为目标函数的一部分。

核心技巧是使用 惩罚函数法 。思路是：违反约束的行为会导致目标函数值变差（被惩罚），从而在优化过程中被自动排除。

1. 构造等式约束 ：首先，将不等式约束 Σ aᵢ xᵢ ≤ b 转化为等式。我们引入一个非负的 松弛变量 S，使得： Σ aᵢ xᵢ + S = b， 其中 S ≥ 0。 这个S代表了背包的“剩余空间”。

2. 离散化松弛变量 ：为了适配0/1变量模型，我们需要将连续变量S用一组0/1变量来表示。一个有效的方法是采用 二进制展开 。假设我们预估剩余空间不会超过一个最大值S_max，我们可以用m+1个比特位y₀, y₁, ..., yₘ来表示S： S = Σ_{k=0}^{m} 2^k yₖ， 其中 yₖ ∈ {0, 1}。 这样，S就可以表示从0到(2^{m+1}-1)之间的任意整数，其精度和范围由m决定。

3. 构建惩罚项 ：现在，我们有了一个等式约束：Σ aᵢ xᵢ + Σ 2^k yₖ - b = 0。将其平方，并乘以一个足够大的 惩罚系数P ，加入到原始的目标函数中： 新目标函数 H = (原始价值函数) - P * (Σ aᵢ xᵢ + Σ 2^k yₖ - b)² 。

   这里的逻辑是：如果等式被完美满足（括号内为0），惩罚项为0，不影响目标值。如果等式不满足（即违反容量约束），括号内不为零，平方后为正数，再乘以大的正数P，就会使总目标函数H的值大幅减小（因为我们是在求最大化，等价于在求-H的最小化）。在优化过程中，算法为了最大化H（或最小化-H），会极力避免违反约束的情况。

实操心得： 惩罚系数P的选择至关重要。P太小，约束“力度”不够，可能得到违反约束的“伪最优解”；P太大，可能会使优化地形过于陡峭，增加求解难度。通常，P需要设定为略大于目标函数中价值系数绝对值之和的量级，这是一个需要根据具体问题调优的参数。

经过以上步骤，我们成功地将一个带约束的二次背包问题，转化为了一个 无约束二次二进制优化问题 ，其标准形式为： 最小化 H(x, y) = Σᵢⱼ Qᵢⱼ zᵢ zⱼ ， 其中 z 是所有变量x和y组成的向量，取值为0或1。 这就是所谓的 QUBO 模型，它与 Ising 模型（变量取值为±1）仅存在简单的线性变换关系，是量子退火机和相干光量子计算机等设备直接求解的对象。

3. 实例拆解：一步步构建与求解QUBO模型

让我们通过一个具体例子，将上述建模过程具象化。假设我们有4件物品待选，其重量a和价值c如下，背包容量b=6。为简化，我们先考虑独立价值（即vᵢⱼ在i≠j时为0），但方法完全通用。

物品i	重量 aᵢ	价值 cᵢ
1	2	3
2	3	4
3	3	5
4	4	6

步骤1：建立基础模型 目标：最大化 3x₁ + 4x₂ + 5x₃ + 6x₄ 约束：2x₁ + 3x₂ + 3x₃ + 4x₄ ≤ 6 变量：x₁, x₂, x₃, x₄ ∈ {0, 1}

步骤2：引入松弛变量并二进制化 容量b=6，最大可能剩余空间不会超过6。我们可以用3个比特位（2²=4, 2¹=2, 2⁰=1）来表示0到7之间的整数，足够覆盖剩余空间S。设 S = 4y₂ + 2y₁ + 1y₀。 则等式约束为：2x₁ + 3x₂ + 3x₃ + 4x₄ + (4y₂+2y₁+y₀) = 6。 移项得：2x₁ + 3x₂ + 3x₃ + 4x₄ + 4y₂ + 2y₁ + y₀ - 6 = 0。

步骤3：构造惩罚项并得到QUBO模型 令惩罚系数 P = 10（此例中价值系数较小，P=10足够大）。 惩罚项为：10 * (2x₁ + 3x₂ + 3x₃ + 4x₄ + 4y₂ + 2y₁ + y₀ - 6)²。 QUBO模型的目标是 最小化 以下哈密顿量H： H = - (3x₁ + 4x₂ + 5x₃ + 6x₄) + 10 * (2x₁ + 3x₂ + 3x₃ + 4x₄ + 4y₂ + 2y₁ + y₀ - 6)²。

步骤4：展开、化简与矩阵表示 将平方项展开是一个繁琐但机械的过程。展开后，会得到所有变量两两相乘的项（如 x₁x₂, x₁y₀等）和线性项。利用0/1变量的性质 xᵢ² = xᵢ（因为0²=0, 1²=1），可以将平方项合并到线性项中。 最终，H可以写成紧凑的二次型形式： H = zᵀ Q z ， 其中 z = [x₁, x₂, x₃, x₄, y₀, y₁, y₂]ᵀ 是一个7维的0/1变量向量，Q是一个7x7的上三角（或对称）矩阵。

通过计算（此处省略详细代数展开），我们可以得到这个Q矩阵。求解这个QUBO模型，即寻找使H最小的z向量。

步骤5：求解与解释 通过经典求解器（如模拟退火、分支定界）或量子启发式求解器对该QUBO模型进行求解，可以得到最优解。对于这个简单例子，最优解很可能是： x₁ = 1, x₂ = 0, x₃ = 1, x₄ = 0, y₀ = 1, y₁ = 0, y₂ = 0。 解释：

• 选择了物品1（重2值3）和物品3（重3值5），总重量为5，总价值为8。
• 松弛变量 y₀=1, y₁=0, y₂=0，代表剩余空间 S = 1，满足 2+3+1=6 的等式约束。
• 验证：这是否是全局最优？我们看看其他组合：选物品2和3（重6值9）似乎价值更高，但重量6已满，剩余空间S=0，需要验证在QUBO模型下其能量是否更低。这需要代入完整的H公式计算。实际上，由于我们惩罚系数P设置得当，违反约束的方案（如多选一件物品）其惩罚成本将远超获得的价值增益，因此在优化中会被淘汰。

这个例子清晰地展示了从实际问题到QUBO模型，再到求解的完整链条。对于“天工量子大脑”这样的设备，其硬件底层就是为快速寻找这种QUBO/Ising模型的最低能态（即最小化H）而设计的。

4. 量子计算求解的优势与挑战

4.1 为何量子计算有潜力

传统计算机处理此类组合优化问题，其计算时间随问题规模（物品数n）指数增长（O(2ⁿ)）。量子计算，特别是利用量子退火或相干量子随机游走等原理的专用量子优化机器，其核心优势在于 利用量子叠加和量子隧穿效应来同时探索多个候选解 。

1. 量子叠加 ：n个量子比特可以同时处于2ⁿ种状态的叠加中。在求解过程中，相当于同时评估大量可能的物品组合。
2. 量子隧穿 ：在优化地形中，传统算法可能被困在局部最优解（像一个山谷）。量子隧穿效应允许算法以一定概率“穿过”能量壁垒，探索到更深的全局最优山谷，从而更有可能找到全局最优解。

“天工量子大脑”采用的相干光量子计算路径，利用光子的量子特性来构建和求解Ising模型。其宣称的毫秒级求解速度，正是针对映射好的QUBO模型而言。它避免了传统通用计算机的串行指令循环，通过物理系统的自然演化来寻找低能态。

4.2 当前面临的实践挑战

尽管原理诱人，但将现实世界的背包问题交给量子计算机求解，仍需克服几个关键挑战：

1. 建模与编码开销 ：如上文所示，将一个问题转化为等价的QUBO模型需要引入额外的松弛变量。一个简单的n物品背包问题，可能会编码成n+m个比特的QUBO问题。这占用了宝贵的量子比特资源。如何更紧凑、更高效地建模，是一个重要的研究课题。

2. 精度与噪声 ：目前的量子计算设备存在噪声，量子比特的相干时间有限。这可能导致求解结果出现偏差，或无法稳定地输出绝对最优解。对于价值差异微小的近优解，设备可能难以分辨。

3. 问题规模限制 ：尽管100量子比特相比早期是巨大进步，但相对于许多工业级优化问题（变量成千上万），其可直接求解的规模仍然有限。需要通过问题分解、经典-量子混合算法等策略来应对更大规模问题。

4. 算法与软件的成熟度 ：整个量子优化软件栈，包括编译器（将问题映射到硬件）、控制软件、结果后处理与分析工具，都处于早期阶段，需要与硬件同步发展。

5. 常见问题与拓展思考

5.1 经典算法与量子方法的对比

面对背包问题，我们并非只有量子这一条路。下表对比了几种主流方法：

方法	原理简述	优势	局限性	适用场景
动态规划	将问题分解为子问题，存储中间结果避免重复计算。	能获得精确最优解；对于整数重量/价值，效率较高。	“维度灾难”：当容量或物品数量极大时，所需内存/时间激增。	物品数量不多，重量和价值为整数的中等规模问题。
分支定界	系统性地枚举搜索树，利用上下界剪枝，排除不可能的分支。	能获得精确最优解；通过剪枝大幅减少搜索量。	最坏情况下仍需遍历大量组合；性能严重依赖边界估计质量。	中等规模问题，价值/重量差异较大时剪枝效果好。
启发式算法 (如遗传算法、贪婪算法)	基于直观或经验构造规则，快速获得可行解。	速度快，可处理超大规模问题；实现相对简单。	不能保证获得全局最优解；解的质量可能不稳定。	对最优解要求不严，追求快速响应的超大规模问题。
量子启发/量子计算	利用量子物理原理（叠加、隧穿）探索解空间。	有潜力跳出局部最优；针对特定模型（Ising/QUBO）硬件加速显著。	硬件处于发展早期；编码开销大；受噪声影响。	对全局最优有强烈需求的中等规模问题；作为经典算法的补充或加速部件。

个人体会： 在实际项目中，不要陷入“非此即彼”的思维。更现实的路径是“ 量子经典混合 ”。例如，用经典启发式算法快速得到一个优质初始解，再用量子退火机在其邻域进行精细搜索；或者将大规模问题分解为多个子问题，其中关键且规模合适的子问题交由量子设备求解。玻色量子启动“燎原计划”开发者平台，正是为了推动这种混合模式的探索和应用。

5.2 背包问题变种与建模适应性

文中提到的多重背包、无界背包等变种，其QUBO建模思路是相通的，核心在于如何用0/1变量刻画选择。

• 多重背包 ：如果物品i最多可选kᵢ件，可以将其拆分为kᵢ个相同的虚拟物品，每个虚拟物品重量和价值相同，但视为独立可选。这会增加变量数。
• 无界背包 ：理论上可选无限件，在实际建模中必须设定一个合理的上限（基于背包容量），然后按多重背包处理。
• 分数背包 ：这是唯一一个可以用贪心算法在多项式时间内获得最优解的特例，通常不需要用到复杂的整数规划或量子计算。
• 有约束背包 ：额外的约束（如物品A和B不能同时选）可以通过添加惩罚项到QUBO目标函数中轻松实现。例如，添加一个大的正惩罚项 +P * x_A * x_B ，当两者同时为1时，目标函数会变差，从而抑制这种组合。

5.3 对开发者和研究者的建议

如果你有兴趣尝试用量子计算解决优化问题，可以从以下几点入手：

1. 从理解问题开始 ：深入理解你的业务问题，明确优化目标、约束条件，以及“价值”和“重量”的具体含义。这是正确建模的基石。
2. 掌握建模工具 ：学习如何使用QUBO或Ising模型对问题进行表述。有许多开源库（如D-Wave的 dimod ，富士通的 DA 库）提供了高级API，可以帮助你构建模型。
3. 利用云平台 ：积极利用像“燎原计划”这样的真机测试平台。从中小规模的问题开始，熟悉整个流程：问题建模 -> 提交任务 -> 获取结果 -> 分析验证。
4. 建立基准对比 ：始终用经典算法（如Gurobi, CPLEX等商业求解器，或开源启发式算法库）为你的问题建立一个性能基准。量子求解器的价值需要在对比中体现。
5. 关注混合算法 ：研究如何将量子计算模块嵌入到经典的算法框架中。例如，用量子设备为遗传算法生成优质初始种群，或用量子退火来优化机器学习中的超参数。

量子计算解决组合优化问题，目前正从实验室演示走向实用化探索的早期阶段。它并非要取代所有经典算法，而是为解决那些经典计算机力有未逮的、对全局最优解有苛刻要求的特定难题，提供一种新的工具和可能性。背包问题作为一个经典的试金石，清晰地展示了这条技术路径的逻辑：将现实难题抽象为数学模型，再将数学模型“编译”成物理设备可执行的“指令”。这个过程本身，就是一次深刻的跨学科思维训练。随着硬件能力的提升和算法工具的完善，我们有望在物流调度、金融风控、材料发现等领域，看到越来越多由量子计算赋能的高效解决方案。