1. 项目概述量子退火作为解决组合优化问题的一种前沿量子算法近年来备受关注。它的核心思想是将一个复杂的优化问题映射成一个物理系统的能量模型——伊辛模型然后通过量子演化让系统自然地“退火”到能量最低的基态这个基态对应的自旋构型就是我们要找的最优解。听起来很酷对吧理论上很多NP难问题比如旅行商问题、蛋白质折叠、投资组合优化都能用这套框架来建模。然而理想很丰满现实却很骨感。当我们兴冲冲地把精心构建的伊辛模型塞进D-Wave这类商用量子退火硬件时常常会发现拿到的解质量不尽如人意甚至和经典算法比都没啥优势。问题出在哪一个关键瓶颈在于硬件的数值精度限制。你可以把量子退火器想象成一个精度有限的“计算器”。它只能接受特定范围内的磁场和耦合系数比如D-Wave Advantage的磁场系数范围是[-4, 4]耦合系数范围是[-2, 1]。如果你的问题模型里有的系数非常大比如惩罚项系数λ10000有的系数又非常小比如一个微弱的相互作用J0.001那么为了把整个模型塞进硬件允许的范围你必须对整个哈密顿量进行整体缩放。缩放后那些原本就很小的系数会变得微乎其微甚至低于硬件的噪声水平。硬件控制误差、热噪声等扰动会轻易地“淹没”这些微小信号导致系统演化到错误的“基态”输出垃圾解。因此动态范围最大系数与最小非零系数之比成了衡量问题对硬件噪声敏感度的一个关键指标。动态范围越大缩放后的小系数就越脆弱解的质量就越可能受影响。为了应对这个问题学术界提出了几种系数缩减方法目标就是在问题映射到硬件之前通过数学变换把那些特别大的系数“拆解”或“压缩”从而降低整个模型的动态范围理论上能提升硬件求解的鲁棒性。但是这里存在一个理论与实践的巨大鸿沟几乎所有关于系数缩减的前期研究都忽略了一个在实际操作中必不可少的步骤——次要嵌入。由于实际量子退火硬件的量子比特连接拓扑是稀疏的比如Pegasus图而我们问题模型的交互图往往很稠密无法直接映射。次要嵌入就是通过将逻辑变量问题变量用一“链”物理量子比特来表示从而在稀疏的硬件图上“模拟”出稠密的逻辑连接。这个过程本身就会改变哈密顿量的系数逻辑上的大系数在嵌入后可能会被分摊到多个物理耦合上而变小同时为了维持链内量子比特状态一致而引入的链强度参数本身就是一个很大的耦合系数它可能成为新的动态范围主导者。所以一个很自然的问题就来了那些在逻辑层面被证明有效的系数缩减方法在经历了次要嵌入这个“现实滤镜”之后还能不能真正改善从真实硬件上采样的解的质量这正是我们这次要深入探讨的核心。本文将带你重新审视三种主流的系数缩减方法——交互扩展方法、有界系数整数编码和增广拉格朗日法——在次要嵌入的约束下究竟表现如何。我们会用真实的D-Wave Advantage硬件实验数据说话告诉你哪些方法真的有用哪些可能只是“纸上谈兵”并分享我们在实验过程中踩过的坑和总结出的实用经验。2. 核心原理与背景知识拆解在深入实验细节之前我们有必要把几个关键概念和它们之间的关联彻底理清。这能帮助你看懂后续的实验设计并理解为什么有些方法会失效。2.1 量子退火与伊辛模型从问题到物理量子退火解决组合优化问题的标准流程可以概括为“建模-编码-退火-解码”。建模 将你的优化问题比如最大割、旅行商转化为一个二次无约束二进制优化问题或者等价的伊辛模型。伊辛模型的哈密顿量长这样H Σ_{i,j} J_{ij} σ_i σ_j Σ_i h_i σ_i其中σ_i 是自旋变量取值为1或-1对应二进制变量0或1。J_{ij} 是耦合系数描述自旋i和j之间的相互作用强度h_i 是局域磁场系数。问题的解对应这个哈密顿量的基态能量最低的状态。编码与次要嵌入 这是连接抽象模型和真实硬件的桥梁。由于硬件量子比特的连接性是固定的、稀疏的图结构比如Chimera, Pegasus而你的问题交互图可能是完全图或任意稠密图无法直接实现。次要嵌入就是解决这个拓扑不匹配问题的技术。它把逻辑变量对应问题中的一个自旋σ_i映射到硬件上的一个链上这个链由多个物理量子比特组成它们之间通过很强的负耦合链耦合连接迫使它们在最终解中取相同的值。嵌入后的物理哈密顿量包含了三部分继承自原问题的物理场和链间耦合以及新引入的链内耦合。退火与采样 将嵌入后的哈密顿量参数h_i, J_{ij}, 链强度提交给量子退火器。机器从一个简单的初始哈密顿量开始缓慢演化到代表你问题的目标哈密顿量最后测量所有量子比特的状态得到一个候选解。解码 由于链断裂链内量子比特取值不一致的存在需要对采样结果进行修复比如多数表决然后将物理比特的状态映射回逻辑变量得到最终解。注意 链强度的选择是一门艺术也是影响性能的关键。强度太小链容易断裂解不可用强度太大它会成为哈密顿量中的绝对主导项在缩放时挤压其他有意义的相互作用系数使其低于噪声水平同样导致解质量下降。寻找最优链强度本身就是个需要调参的优化问题。2.2 硬件精度误差动态范围的致命影响当前量子退火硬件如D-Wave的模拟控制精度有限。输入系数需要被缩放到硬件指定的范围内[h-, h]和[J-, J]。缩放因子s_H max(s_h, s_J)其中s_h max(max_i h_i / h, min_i h_i / h-)s_J同理。缩放后的哈密顿量为H H / s_H。假设你的原始哈密顿量中有一个很小的耦合J_small 0.01而最大系数J_large 100那么s_H至少是100 / J。缩放后J_small会变成0.01 / s_H这个值可能小到和硬件噪声δJ估计在1%-5%量级一个水平甚至更小。此时实际的哈密顿量变成了H H δH噪声δH足以改变基态导致机器找到错误的“最优解”。动态范围DR s_H / min(|nonzero coefficients|)直观地衡量了这种脆弱性。DR越大小系数在缩放后就越微不足道越容易被噪声淹没。系数缩减方法的核心目标就是降低这个动态范围。2.3 被忽视的关键次要嵌入如何改变游戏规则大部分系数缩减的研究都在逻辑哈密顿量层面进行但忽略了次要嵌入带来的三个根本性变化系数分摊 逻辑磁场系数h_i在嵌入后会被分摊到其对应链上的所有物理比特上。通常采用平均分配\tilde{h}_k h_i / |C(i)|。这意味着逻辑层面的大磁场系数在物理层面会自动被缩小。这是一个非常重要的发现它暗示我们也许我们根本不需要费力去缩减逻辑磁场系数。新的大系数来源——链强度 为了保持链的一致性而引入的链内耦合J_c其绝对值即链强度通常被设置为一个很大的负数。在大数实际问题中最优链强度的绝对值往往会超过最大的逻辑耦合系数。也就是说嵌入后物理哈密顿量的动态范围很可能由链强度主导而不是原始问题中的大系数。链间耦合也可能被分摊 如果逻辑耦合J_{ij}对应的链间连接有多条|S(i,j)| 1那么J_{ij}也会被分摊到这些连接上但这在实际嵌入中不常见。因此评估一个系数缩减方法的有效性不能只看它在逻辑层面把J_max从100降到了10还必须看它能否最终降低物理哈密顿量中的最大系数而这个最大系数很可能就是链强度。如果链强度没有成比例地下降那么动态范围的缩减就是徒劳的。这就是我们本次研究的出发点在次要嵌入的约束下系统地评估系数缩减方法对物理耦合系数尤其是链强度和最终采样质量的实际影响。3. 三种系数缩减方法深度解析与实操要点我们重点评测了三种具有代表性的系数缩减方法。理解它们的原理、适用场景和潜在开销是判断其实际价值的关键。3.1 交互扩展方法暴力拆分强耦合核心思想 如果一个耦合系数J_{ij}太大了我就把它“拆散”。通过引入辅助变量将一个强相互作用分解为多个弱相互作用的和同时保证问题的基态不变忽略辅助变量的取值。具体操作 假设我们想将正耦合系数的上限限定为M。对于每个超过M的J_{ij} M计算k_{ij} ceil(J_{ij} / M)。然后将原哈密顿量中的项J_{ij} σ_i σ_j替换为(J_{ij} / k_{ij}) * σ_i σ_j Σ_{l1}^{k_{ij}-1} (J_{ij} / k_{ij}) * σ_i σ_{ij}^{(l)} - Σ_{l1}^{k_{ij}-1} (J_{ij} / k_{ij}) * σ_j σ_{ij}^{(l)}其中σ_{ij}^{(l)}是新引入的辅助自旋变量。这个过程相当于用一条长度为k_{ij}的路径包含辅助节点来“模拟”原来的单条强边路径上每条边的权重都是J_{ij} / k_{ij}。优点与代价优点 通用性强适用于任何伊辛模型。能严格保证缩减后模型的基态与原模型一致在忽略辅助变量意义下。代价变量数量会显著增加。每个需要缩减的耦合都会引入k_{ij} - 1个辅助变量。如果问题中有大量强耦合变量膨胀会非常严重这不仅增加了嵌入的难度需要更多物理比特和更长的链也可能引入新的复杂性和误差。实操心得 IEM 就像“精雕细琢”它确实能降低动态范围但代价是问题规模膨胀。在实际使用中需要权衡M的选择。M设得太小变量爆炸M设得太大缩减效果有限。一个实用的策略是先将系数归一化到硬件范围附近然后只对那些仍然远超平均水平的“异常值”耦合应用 IEM。3.2 有界系数整数编码控制整数展开的系数增长核心思想 很多组合优化问题包含整数变量例如表示资源使用量。在转化为QUBO时我们需要用多个二进制变量线性组合来表示一个整数变量z c Σ_i (a_i / 2) σ_i。不同的编码方式如二进制编码、一元编码在变量数量和系数大小上有不同的权衡。二进制编码最节省变量但系数a_i可以呈指数增长2^i。BCE 方法旨在控制系数a_i的上界μ在变量数量和系数大小之间取得平衡。具体操作 对于一个在区间[L, U]内的整数变量z给定上界参数μBCE 会生成一组系数{a_i}满足a_i ≤ μ并且用尽可能少的二进制变量来表示整个区间。算法混合了二进制编码对于低位和“封顶”编码对于高位系数保持为μ。优点与代价优点 专门针对整数变量展开导致的平方项大系数问题。当目标函数中包含z^2项时常见于带约束的问题如(Σ_i b_i x_i - z)^2BCE 可以一次性避免由大a_i相乘产生的巨大耦合系数而 IEM 处理这种密集的大系数会非常低效。代价 为了限制系数大小需要比纯二进制编码更多的变量。变量数量的增加是O(D/μ)其中D U - L是整数范围。注意事项 BCE 的效果高度依赖于问题形式。它主要解决由整数变量平方项产生的系数爆炸。如果问题中最大的系数来自其他部分比如惩罚项系数λ那么 BCE 可能收效甚微。在我们的实验中MKP问题就出现了这种情况。3.3 增广拉格朗日法软化约束降低惩罚核心思想 很多问题中的大系数来源于约束条件的惩罚项。例如等式约束Σ_i b_i σ_i c通常被转化为惩罚项λ (Σ_i b_i σ_i - c)^2其中惩罚系数λ需要足够大以保证约束被满足但过大的λ会导致动态范围激增。ALM 通过引入拉格朗日乘子u将惩罚项改为u * g(σ) λ * g(σ)^2其中g(σ) Σ_i b_i σ_i - c。通过迭代更新u和λ可以在较小的λ下也能施加足够的惩罚力。另一种视角——约束扰动 ALM 公式可以重写为λ * (g(σ) - ϵ)^2其中ϵ -u/(2λ)。这可以理解为将原始约束g(σ)0松弛为g(σ)ϵ。只要扰动|ϵ|足够小对于二进制/自旋变量通常要求|ϵ| 0.5最小化新惩罚项的解依然会近似满足原约束。通过选择合适的ϵ可以在不增加λ的情况下增加对不可行解的惩罚。优点与代价优点 直接针对惩罚系数这一常见的大系数来源。理论上可以显著降低所需的λ。代价 引入了新的参数u或ϵ需要额外的调参或迭代过程。其效果在理论上不如 IEM 那样确定并且如我们的实验所示在次要嵌入后其效果可能会发生意想不到的变化甚至失效。关键发现 我们的实验揭示了一个重要现象ALM 在逻辑层面不使用次要嵌入用模拟退火测试确实能降低惩罚系数并保持可行性。但一旦经过次要嵌入在真实量子退火硬件上这种改善就消失了甚至可行性率会下降。这表明次要嵌入过程可能会改变惩罚项在能量景观中的局部结构使得扰动ϵ的积极作用被抵消或逆转。这是一个非常值得警惕的发现意味着在逻辑层面有效的技巧在硬件层面可能需要重新评估。4. 实验设计与结果分析在真实硬件上验证理论说得再好也要实验来检验。我们设计了一系列实验使用 D-Wave Advantage 量子退火器在标准的 QUBO、MKP 和 QAP 问题实例上系统地评估了上述方法。4.1 实验一物理磁场系数真的需要缩减吗目标 验证在次要嵌入后物理磁场系数是否仍然是硬件精度的瓶颈。方法 我们在包含126个实例的 MQLIB QUBO 基准数据集上进行了分析。对于每个实例找到其在 Pegasus 图上的次要嵌入或估算然后计算物理磁场系数的缩放因子s_̃h和逻辑耦合系数的缩放因子s_J。核心发现在绝大多数116/126实例中都满足s_̃h ≤ s_J。这意味着物理磁场系数在缩放后普遍小于或等于逻辑耦合系数。在少数例外gka.*b 系列中我们进一步计算了包含最优链强度在内的物理耦合缩放因子s_̃J发现除了一个边缘情况s_̃h / s_̃J ≈ 1.05其余均满足s_̃h ≤ s_̃J。结论对于实际形式化为 QUBO 的问题在次要嵌入物理磁场系数很少成为限制硬件精度的主要因素。因此专注于缩减逻辑磁场系数很可能是没有必要的。这一发现解放了我们的思路我们可以放心地使用那些可能会增大磁场系数但能有效降低耦合系数的方法如 ALM而不必担心磁场成为新的瓶颈。4.2 实验二IEM 的有效性验证目标 验证 IEM 在次要嵌入后能否降低链强度并提升采样质量。实验设计简单问题 构造一个三自旋的简单伊辛模型H σ1σ2 (1/J) σ2σ3。当J很大时如512小项1/J容易被噪声淹没导致找到错误基态的概率接近50%。我们应用 IEM 将最大耦合系数从J缩减到更小的Ĵ然后进行嵌入和采样。基准问题 在 MQLIB 的 gka.1b, gka.2b, gka.3b 实例上测试。这些实例的耦合系数在 [1,50] 均匀分布且物理磁场系数相对较大。我们设置不同的上限Ĵ进行缩减。结果与分析简单问题 结果非常清晰。随着Ĵ减小即系数缩减程度增加找到正确基态的概率P_opt显著上升。当Ĵ1或2时P_opt接近1。同时最优链强度也大致与Ĵ成比例下降。这证明了 IEM 在理想情况下是有效的。基准问题 结果更具启发性。对于 gka.2b 和 gka.3b存在一个最优的Ĵ分别为40和30使得采样能量最低效果优于原始问题Ĵ50。然而Ĵ并非越小越好。当Ĵ过小如10或20时由于引入了大量辅助变量问题规模膨胀嵌入质量下降反而导致性能恶化。同时最优链强度也随着有效缩减而降低。关键验证 即使在应用 IEM 缩减耦合后我们检查了这些实例的s_̃h和s_̃J发现s_̃h ≤ s_̃J依然成立。这再次印证了实验一的结论并说明 IEM 的耦合缩减不会意外导致磁场成为瓶颈。实操要点IEM 是一把双刃剑。它能有效降低动态范围但以增加变量为代价。存在一个“甜点” 需要权衡系数缩减的收益和变量增加带来的开销。盲目追求极致的系数缩减Ĵ很小可能适得其反。链强度同步缩减 实验证实当逻辑耦合系数被成功缩减后所需的最优链强度也会成比例下降这是性能提升的关键机制。4.3 实验三BCE 在整数编码中的表现目标 评估 BCE 在控制整数变量展开导致的系数爆炸方面的效果。实验设计简单整数问题 最小化(z-1)^2z在 [0,191] 区间。使用不同的上界参数μ进行 BCE 编码。实际 MKP 问题 选择 weing1 和 weish06 两个标准 MKP 实例。问题中包含整数变量z_i来表示资源使用量其平方项会产生大系数。我们测试不同的μ值。结果与分析简单问题 BCE 效果显著。随着μ减小系数上界降低最优链强度线性下降采样到基态的概率P_opt在μ16时达到峰值超过10%远高于二进制编码μ64。然而μ过小如2也会因变量过多而性能下降。这展示了 BCE 在理想场景下的潜力。MKP 问题 结果令人失望。尽管 BCE 成功降低了逻辑耦合系数s_J但最优链强度几乎没有变化weing1或仅轻微下降weish06。相应地采样质量无论是能量还是可行解的目标值也未观察到明显改善。深度解读与避坑指南 为什么 BCE 在 MKP 上失效我们分析可能有以下原因链强度由其他项主导 在 MKP 的 QUBO 形式-Σ p_j x_j λ Σ (Σ w_ij x_j - z_i)^2中展开后除了z_i^2项还有x_j x_{j}的交叉项系数为λ * w_ij * w_{ij}。这些交叉项可能产生了比z_i^2项更大的系数成为链强度的决定因素。BCE 只控制了z_i的展开系数却管不了这些交叉项。问题结构复杂性 真实问题的能量景观比简单玩具问题复杂得多。链强度的选择不仅取决于最大系数还取决于整个能量分布的“粗糙度”。仅仅降低一部分系数可能不足以改变链强度的最优值。重要教训 BCE 并非“银弹”。它的有效性严重依赖于问题结构。在应用 BCE 之前务必分析你的 QUBO 模型中最大的系数究竟来自哪里。如果最大的系数并非来自整数变量的平方项那么 BCE 可能收效甚微。一个实用的检查方法是在编码后计算并比较逻辑哈密顿量中不同来源的系数绝对值大小。4.4 实验四ALM 的“理想与现实”目标 探究 ALM惩罚项扰动在次要嵌入前后的效果差异。实验设计 使用两个小型 QAP 实例nug5, tai5a。我们引入扰动ϵ将约束Σ x_{ij} 1的惩罚项改为λ (Σ x_{ij} - 1 - ϵ)^2。在ϵ从 0 到 0.5 的范围内进行测试。实验分两步无次要嵌入模拟退火 SA 作为基线验证 ALM 在理想条件下的效果。有次要嵌入量子退火 QA 在真实硬件流程中测试。结果与分析SA 结果理想情况 与理论预期一致。当施加正扰动ϵ 0时可以用更小的惩罚系数λ达到与ϵ0时相近甚至更高的可行性率。同时在可行性得以维持的情况下更小的λ带来了更好的目标函数值。这证明了 ALM 在逻辑层面的有效性。QA 结果实际情况 出现了戏剧性的反转。在次要嵌入后扰动ϵ不仅没有帮助降低所需的λ反而导致可行性率几乎单调下降。在相同的λ下ϵ越大得到的可行解越少。目标函数值也未因扰动而改善。问题排查与根源分析 为了区分是量子退火器本身的问题还是次要嵌入导致的问题我们增加了一组对照实验使用 SA 来求解经过次要嵌入后的物理哈密顿量。结果与量子退火的结果高度相似。这说明性能下降的根源在于次要嵌入过程本身。我们的推断 次要嵌入改变了问题的局部连接结构。惩罚项(g(σ)-ϵ)^2在逻辑层面是一个全局性的约束。但在嵌入后这个约束被“打散”并分配到了许多局部的链间耦合上。扰动ϵ可能微妙地改变了这些局部相互作用的平衡使得链在演化过程中更容易断裂或者使得满足扰动后约束的低能量态在嵌入后的能量景观中不再占优。这揭示了算法层技巧与硬件底层实现之间存在复杂的相互作用在逻辑层面有效的优化经过硬件映射后可能会失效甚至起反作用。5. 总结、经验与未来展望通过这一系列在真实量子退火硬件上进行的、严格考虑次要嵌入影响的实验我们得到了几个清晰且具有实践指导意义的结论磁场系数缩减通常非必需 次要嵌入过程天然地分摊了逻辑磁场系数。在绝大多数实际QUBO问题中物理磁场系数在缩放后不会大于耦合系数。因此研发新的系数缩减方法时可以优先考虑降低耦合系数即使这可能以增大磁场系数为代价。IEM 是可靠的选择但需谨慎使用 交互扩展方法能有效降低逻辑耦合系数并传导至物理链强度从而提升采样质量。关键是要找到系数缩减与变量增加之间的最佳平衡点无脑追求最小动态范围会导致问题规模膨胀反而损害性能。BCE 效果高度依赖于问题 对于由整数变量平方项主导系数动态范围的简单问题BCE 效果显著。但对于像 MKP 这样的实际问题其他交互项可能成为主导导致 BCE 效果限。在使用 BCE 前务必对问题哈密顿量的系数构成进行剖面分析。ALM 在硬件层面可能失效 增广拉格朗日法或惩罚项扰动在逻辑层面是有效的但次要嵌入可能会破坏其作用机制。这给我们的警示是任何在经典模拟或逻辑层面验证有效的预处理技巧都必须放到完整的硬件流程包含次要嵌入中重新验证。给实践者的建议诊断先行 在尝试任何系数缩减之前先对你的问题执行一次完整的嵌入流程分析物理哈密顿量的缩放因子s_̃h和s_̃J。如果s_̃h明显小于s_̃J那么你的优化重点就应该放在耦合项上。链强度是关键观测指标 评估一个系数缩减方法是否有效不能只看逻辑系数的变化一定要观察最优链强度是否随之成比例下降。如果链强度纹丝不动那么解质量大概率也不会改善。从 IEM 开始尝试 如果你的问题动态范围很大且大系数散布在多个耦合项中IEM 是一个相对稳妥的起点。通过网格搜索寻找一个合适的系数上限M。对“魔法”方法保持怀疑 像 ALM 这样参数敏感、机制复杂的方法在应用到真实硬件前务必用你的具体问题实例在嵌入前后都做充分的测试。不要假设在 SA 上有效的技巧在 QA 上一定有效。未来可能的方向 本次研究也开辟了一些新的思考路径开发嵌入感知的系数缩减方法 既然次要嵌入会改变系数分布能否在设计缩减方法时就考虑嵌入的特性例如能否在嵌入算法中主动将大系数项分配到更长的链上以利用分摊效应自然缩减它探索非基态保持的启发式方法 我们目前的评估框架并不要求缩减方法严格保持基态。未来可以探索那些可能轻微改变解空间但能极大降低动态范围的启发式方法并在我们的框架下量化其“实用价值”——即用解质量的微小损失换取成功率的巨大提升是否值得。系数缩减与纠错编码的结合 量子退火纠错码需要消耗大量额外比特。能否将系数缩减作为减少 QAC 开销的一种预处理或者在存在 QAC 的情况下系数缩减的收益是否会发生变化量子退火硬件仍在快速发展精度在不断提升但噪声和限制短期内不会消失。理解并规避硬件精度的限制通过巧妙的预处理提升有用信息的信噪比是将量子优势从理论推向实践不可或缺的一环。希望本文的探索和发现能为你在量子退火的实际应用之路上提供一些切实的参考和避坑指南。
量子退火系数缩减：次要嵌入下的硬件精度优化实践
1. 项目概述量子退火作为解决组合优化问题的一种前沿量子算法近年来备受关注。它的核心思想是将一个复杂的优化问题映射成一个物理系统的能量模型——伊辛模型然后通过量子演化让系统自然地“退火”到能量最低的基态这个基态对应的自旋构型就是我们要找的最优解。听起来很酷对吧理论上很多NP难问题比如旅行商问题、蛋白质折叠、投资组合优化都能用这套框架来建模。然而理想很丰满现实却很骨感。当我们兴冲冲地把精心构建的伊辛模型塞进D-Wave这类商用量子退火硬件时常常会发现拿到的解质量不尽如人意甚至和经典算法比都没啥优势。问题出在哪一个关键瓶颈在于硬件的数值精度限制。你可以把量子退火器想象成一个精度有限的“计算器”。它只能接受特定范围内的磁场和耦合系数比如D-Wave Advantage的磁场系数范围是[-4, 4]耦合系数范围是[-2, 1]。如果你的问题模型里有的系数非常大比如惩罚项系数λ10000有的系数又非常小比如一个微弱的相互作用J0.001那么为了把整个模型塞进硬件允许的范围你必须对整个哈密顿量进行整体缩放。缩放后那些原本就很小的系数会变得微乎其微甚至低于硬件的噪声水平。硬件控制误差、热噪声等扰动会轻易地“淹没”这些微小信号导致系统演化到错误的“基态”输出垃圾解。因此动态范围最大系数与最小非零系数之比成了衡量问题对硬件噪声敏感度的一个关键指标。动态范围越大缩放后的小系数就越脆弱解的质量就越可能受影响。为了应对这个问题学术界提出了几种系数缩减方法目标就是在问题映射到硬件之前通过数学变换把那些特别大的系数“拆解”或“压缩”从而降低整个模型的动态范围理论上能提升硬件求解的鲁棒性。但是这里存在一个理论与实践的巨大鸿沟几乎所有关于系数缩减的前期研究都忽略了一个在实际操作中必不可少的步骤——次要嵌入。由于实际量子退火硬件的量子比特连接拓扑是稀疏的比如Pegasus图而我们问题模型的交互图往往很稠密无法直接映射。次要嵌入就是通过将逻辑变量问题变量用一“链”物理量子比特来表示从而在稀疏的硬件图上“模拟”出稠密的逻辑连接。这个过程本身就会改变哈密顿量的系数逻辑上的大系数在嵌入后可能会被分摊到多个物理耦合上而变小同时为了维持链内量子比特状态一致而引入的链强度参数本身就是一个很大的耦合系数它可能成为新的动态范围主导者。所以一个很自然的问题就来了那些在逻辑层面被证明有效的系数缩减方法在经历了次要嵌入这个“现实滤镜”之后还能不能真正改善从真实硬件上采样的解的质量这正是我们这次要深入探讨的核心。本文将带你重新审视三种主流的系数缩减方法——交互扩展方法、有界系数整数编码和增广拉格朗日法——在次要嵌入的约束下究竟表现如何。我们会用真实的D-Wave Advantage硬件实验数据说话告诉你哪些方法真的有用哪些可能只是“纸上谈兵”并分享我们在实验过程中踩过的坑和总结出的实用经验。2. 核心原理与背景知识拆解在深入实验细节之前我们有必要把几个关键概念和它们之间的关联彻底理清。这能帮助你看懂后续的实验设计并理解为什么有些方法会失效。2.1 量子退火与伊辛模型从问题到物理量子退火解决组合优化问题的标准流程可以概括为“建模-编码-退火-解码”。建模 将你的优化问题比如最大割、旅行商转化为一个二次无约束二进制优化问题或者等价的伊辛模型。伊辛模型的哈密顿量长这样H Σ_{i,j} J_{ij} σ_i σ_j Σ_i h_i σ_i其中σ_i 是自旋变量取值为1或-1对应二进制变量0或1。J_{ij} 是耦合系数描述自旋i和j之间的相互作用强度h_i 是局域磁场系数。问题的解对应这个哈密顿量的基态能量最低的状态。编码与次要嵌入 这是连接抽象模型和真实硬件的桥梁。由于硬件量子比特的连接性是固定的、稀疏的图结构比如Chimera, Pegasus而你的问题交互图可能是完全图或任意稠密图无法直接实现。次要嵌入就是解决这个拓扑不匹配问题的技术。它把逻辑变量对应问题中的一个自旋σ_i映射到硬件上的一个链上这个链由多个物理量子比特组成它们之间通过很强的负耦合链耦合连接迫使它们在最终解中取相同的值。嵌入后的物理哈密顿量包含了三部分继承自原问题的物理场和链间耦合以及新引入的链内耦合。退火与采样 将嵌入后的哈密顿量参数h_i, J_{ij}, 链强度提交给量子退火器。机器从一个简单的初始哈密顿量开始缓慢演化到代表你问题的目标哈密顿量最后测量所有量子比特的状态得到一个候选解。解码 由于链断裂链内量子比特取值不一致的存在需要对采样结果进行修复比如多数表决然后将物理比特的状态映射回逻辑变量得到最终解。注意 链强度的选择是一门艺术也是影响性能的关键。强度太小链容易断裂解不可用强度太大它会成为哈密顿量中的绝对主导项在缩放时挤压其他有意义的相互作用系数使其低于噪声水平同样导致解质量下降。寻找最优链强度本身就是个需要调参的优化问题。2.2 硬件精度误差动态范围的致命影响当前量子退火硬件如D-Wave的模拟控制精度有限。输入系数需要被缩放到硬件指定的范围内[h-, h]和[J-, J]。缩放因子s_H max(s_h, s_J)其中s_h max(max_i h_i / h, min_i h_i / h-)s_J同理。缩放后的哈密顿量为H H / s_H。假设你的原始哈密顿量中有一个很小的耦合J_small 0.01而最大系数J_large 100那么s_H至少是100 / J。缩放后J_small会变成0.01 / s_H这个值可能小到和硬件噪声δJ估计在1%-5%量级一个水平甚至更小。此时实际的哈密顿量变成了H H δH噪声δH足以改变基态导致机器找到错误的“最优解”。动态范围DR s_H / min(|nonzero coefficients|)直观地衡量了这种脆弱性。DR越大小系数在缩放后就越微不足道越容易被噪声淹没。系数缩减方法的核心目标就是降低这个动态范围。2.3 被忽视的关键次要嵌入如何改变游戏规则大部分系数缩减的研究都在逻辑哈密顿量层面进行但忽略了次要嵌入带来的三个根本性变化系数分摊 逻辑磁场系数h_i在嵌入后会被分摊到其对应链上的所有物理比特上。通常采用平均分配\tilde{h}_k h_i / |C(i)|。这意味着逻辑层面的大磁场系数在物理层面会自动被缩小。这是一个非常重要的发现它暗示我们也许我们根本不需要费力去缩减逻辑磁场系数。新的大系数来源——链强度 为了保持链的一致性而引入的链内耦合J_c其绝对值即链强度通常被设置为一个很大的负数。在大数实际问题中最优链强度的绝对值往往会超过最大的逻辑耦合系数。也就是说嵌入后物理哈密顿量的动态范围很可能由链强度主导而不是原始问题中的大系数。链间耦合也可能被分摊 如果逻辑耦合J_{ij}对应的链间连接有多条|S(i,j)| 1那么J_{ij}也会被分摊到这些连接上但这在实际嵌入中不常见。因此评估一个系数缩减方法的有效性不能只看它在逻辑层面把J_max从100降到了10还必须看它能否最终降低物理哈密顿量中的最大系数而这个最大系数很可能就是链强度。如果链强度没有成比例地下降那么动态范围的缩减就是徒劳的。这就是我们本次研究的出发点在次要嵌入的约束下系统地评估系数缩减方法对物理耦合系数尤其是链强度和最终采样质量的实际影响。3. 三种系数缩减方法深度解析与实操要点我们重点评测了三种具有代表性的系数缩减方法。理解它们的原理、适用场景和潜在开销是判断其实际价值的关键。3.1 交互扩展方法暴力拆分强耦合核心思想 如果一个耦合系数J_{ij}太大了我就把它“拆散”。通过引入辅助变量将一个强相互作用分解为多个弱相互作用的和同时保证问题的基态不变忽略辅助变量的取值。具体操作 假设我们想将正耦合系数的上限限定为M。对于每个超过M的J_{ij} M计算k_{ij} ceil(J_{ij} / M)。然后将原哈密顿量中的项J_{ij} σ_i σ_j替换为(J_{ij} / k_{ij}) * σ_i σ_j Σ_{l1}^{k_{ij}-1} (J_{ij} / k_{ij}) * σ_i σ_{ij}^{(l)} - Σ_{l1}^{k_{ij}-1} (J_{ij} / k_{ij}) * σ_j σ_{ij}^{(l)}其中σ_{ij}^{(l)}是新引入的辅助自旋变量。这个过程相当于用一条长度为k_{ij}的路径包含辅助节点来“模拟”原来的单条强边路径上每条边的权重都是J_{ij} / k_{ij}。优点与代价优点 通用性强适用于任何伊辛模型。能严格保证缩减后模型的基态与原模型一致在忽略辅助变量意义下。代价变量数量会显著增加。每个需要缩减的耦合都会引入k_{ij} - 1个辅助变量。如果问题中有大量强耦合变量膨胀会非常严重这不仅增加了嵌入的难度需要更多物理比特和更长的链也可能引入新的复杂性和误差。实操心得 IEM 就像“精雕细琢”它确实能降低动态范围但代价是问题规模膨胀。在实际使用中需要权衡M的选择。M设得太小变量爆炸M设得太大缩减效果有限。一个实用的策略是先将系数归一化到硬件范围附近然后只对那些仍然远超平均水平的“异常值”耦合应用 IEM。3.2 有界系数整数编码控制整数展开的系数增长核心思想 很多组合优化问题包含整数变量例如表示资源使用量。在转化为QUBO时我们需要用多个二进制变量线性组合来表示一个整数变量z c Σ_i (a_i / 2) σ_i。不同的编码方式如二进制编码、一元编码在变量数量和系数大小上有不同的权衡。二进制编码最节省变量但系数a_i可以呈指数增长2^i。BCE 方法旨在控制系数a_i的上界μ在变量数量和系数大小之间取得平衡。具体操作 对于一个在区间[L, U]内的整数变量z给定上界参数μBCE 会生成一组系数{a_i}满足a_i ≤ μ并且用尽可能少的二进制变量来表示整个区间。算法混合了二进制编码对于低位和“封顶”编码对于高位系数保持为μ。优点与代价优点 专门针对整数变量展开导致的平方项大系数问题。当目标函数中包含z^2项时常见于带约束的问题如(Σ_i b_i x_i - z)^2BCE 可以一次性避免由大a_i相乘产生的巨大耦合系数而 IEM 处理这种密集的大系数会非常低效。代价 为了限制系数大小需要比纯二进制编码更多的变量。变量数量的增加是O(D/μ)其中D U - L是整数范围。注意事项 BCE 的效果高度依赖于问题形式。它主要解决由整数变量平方项产生的系数爆炸。如果问题中最大的系数来自其他部分比如惩罚项系数λ那么 BCE 可能收效甚微。在我们的实验中MKP问题就出现了这种情况。3.3 增广拉格朗日法软化约束降低惩罚核心思想 很多问题中的大系数来源于约束条件的惩罚项。例如等式约束Σ_i b_i σ_i c通常被转化为惩罚项λ (Σ_i b_i σ_i - c)^2其中惩罚系数λ需要足够大以保证约束被满足但过大的λ会导致动态范围激增。ALM 通过引入拉格朗日乘子u将惩罚项改为u * g(σ) λ * g(σ)^2其中g(σ) Σ_i b_i σ_i - c。通过迭代更新u和λ可以在较小的λ下也能施加足够的惩罚力。另一种视角——约束扰动 ALM 公式可以重写为λ * (g(σ) - ϵ)^2其中ϵ -u/(2λ)。这可以理解为将原始约束g(σ)0松弛为g(σ)ϵ。只要扰动|ϵ|足够小对于二进制/自旋变量通常要求|ϵ| 0.5最小化新惩罚项的解依然会近似满足原约束。通过选择合适的ϵ可以在不增加λ的情况下增加对不可行解的惩罚。优点与代价优点 直接针对惩罚系数这一常见的大系数来源。理论上可以显著降低所需的λ。代价 引入了新的参数u或ϵ需要额外的调参或迭代过程。其效果在理论上不如 IEM 那样确定并且如我们的实验所示在次要嵌入后其效果可能会发生意想不到的变化甚至失效。关键发现 我们的实验揭示了一个重要现象ALM 在逻辑层面不使用次要嵌入用模拟退火测试确实能降低惩罚系数并保持可行性。但一旦经过次要嵌入在真实量子退火硬件上这种改善就消失了甚至可行性率会下降。这表明次要嵌入过程可能会改变惩罚项在能量景观中的局部结构使得扰动ϵ的积极作用被抵消或逆转。这是一个非常值得警惕的发现意味着在逻辑层面有效的技巧在硬件层面可能需要重新评估。4. 实验设计与结果分析在真实硬件上验证理论说得再好也要实验来检验。我们设计了一系列实验使用 D-Wave Advantage 量子退火器在标准的 QUBO、MKP 和 QAP 问题实例上系统地评估了上述方法。4.1 实验一物理磁场系数真的需要缩减吗目标 验证在次要嵌入后物理磁场系数是否仍然是硬件精度的瓶颈。方法 我们在包含126个实例的 MQLIB QUBO 基准数据集上进行了分析。对于每个实例找到其在 Pegasus 图上的次要嵌入或估算然后计算物理磁场系数的缩放因子s_̃h和逻辑耦合系数的缩放因子s_J。核心发现在绝大多数116/126实例中都满足s_̃h ≤ s_J。这意味着物理磁场系数在缩放后普遍小于或等于逻辑耦合系数。在少数例外gka.*b 系列中我们进一步计算了包含最优链强度在内的物理耦合缩放因子s_̃J发现除了一个边缘情况s_̃h / s_̃J ≈ 1.05其余均满足s_̃h ≤ s_̃J。结论对于实际形式化为 QUBO 的问题在次要嵌入物理磁场系数很少成为限制硬件精度的主要因素。因此专注于缩减逻辑磁场系数很可能是没有必要的。这一发现解放了我们的思路我们可以放心地使用那些可能会增大磁场系数但能有效降低耦合系数的方法如 ALM而不必担心磁场成为新的瓶颈。4.2 实验二IEM 的有效性验证目标 验证 IEM 在次要嵌入后能否降低链强度并提升采样质量。实验设计简单问题 构造一个三自旋的简单伊辛模型H σ1σ2 (1/J) σ2σ3。当J很大时如512小项1/J容易被噪声淹没导致找到错误基态的概率接近50%。我们应用 IEM 将最大耦合系数从J缩减到更小的Ĵ然后进行嵌入和采样。基准问题 在 MQLIB 的 gka.1b, gka.2b, gka.3b 实例上测试。这些实例的耦合系数在 [1,50] 均匀分布且物理磁场系数相对较大。我们设置不同的上限Ĵ进行缩减。结果与分析简单问题 结果非常清晰。随着Ĵ减小即系数缩减程度增加找到正确基态的概率P_opt显著上升。当Ĵ1或2时P_opt接近1。同时最优链强度也大致与Ĵ成比例下降。这证明了 IEM 在理想情况下是有效的。基准问题 结果更具启发性。对于 gka.2b 和 gka.3b存在一个最优的Ĵ分别为40和30使得采样能量最低效果优于原始问题Ĵ50。然而Ĵ并非越小越好。当Ĵ过小如10或20时由于引入了大量辅助变量问题规模膨胀嵌入质量下降反而导致性能恶化。同时最优链强度也随着有效缩减而降低。关键验证 即使在应用 IEM 缩减耦合后我们检查了这些实例的s_̃h和s_̃J发现s_̃h ≤ s_̃J依然成立。这再次印证了实验一的结论并说明 IEM 的耦合缩减不会意外导致磁场成为瓶颈。实操要点IEM 是一把双刃剑。它能有效降低动态范围但以增加变量为代价。存在一个“甜点” 需要权衡系数缩减的收益和变量增加带来的开销。盲目追求极致的系数缩减Ĵ很小可能适得其反。链强度同步缩减 实验证实当逻辑耦合系数被成功缩减后所需的最优链强度也会成比例下降这是性能提升的关键机制。4.3 实验三BCE 在整数编码中的表现目标 评估 BCE 在控制整数变量展开导致的系数爆炸方面的效果。实验设计简单整数问题 最小化(z-1)^2z在 [0,191] 区间。使用不同的上界参数μ进行 BCE 编码。实际 MKP 问题 选择 weing1 和 weish06 两个标准 MKP 实例。问题中包含整数变量z_i来表示资源使用量其平方项会产生大系数。我们测试不同的μ值。结果与分析简单问题 BCE 效果显著。随着μ减小系数上界降低最优链强度线性下降采样到基态的概率P_opt在μ16时达到峰值超过10%远高于二进制编码μ64。然而μ过小如2也会因变量过多而性能下降。这展示了 BCE 在理想场景下的潜力。MKP 问题 结果令人失望。尽管 BCE 成功降低了逻辑耦合系数s_J但最优链强度几乎没有变化weing1或仅轻微下降weish06。相应地采样质量无论是能量还是可行解的目标值也未观察到明显改善。深度解读与避坑指南 为什么 BCE 在 MKP 上失效我们分析可能有以下原因链强度由其他项主导 在 MKP 的 QUBO 形式-Σ p_j x_j λ Σ (Σ w_ij x_j - z_i)^2中展开后除了z_i^2项还有x_j x_{j}的交叉项系数为λ * w_ij * w_{ij}。这些交叉项可能产生了比z_i^2项更大的系数成为链强度的决定因素。BCE 只控制了z_i的展开系数却管不了这些交叉项。问题结构复杂性 真实问题的能量景观比简单玩具问题复杂得多。链强度的选择不仅取决于最大系数还取决于整个能量分布的“粗糙度”。仅仅降低一部分系数可能不足以改变链强度的最优值。重要教训 BCE 并非“银弹”。它的有效性严重依赖于问题结构。在应用 BCE 之前务必分析你的 QUBO 模型中最大的系数究竟来自哪里。如果最大的系数并非来自整数变量的平方项那么 BCE 可能收效甚微。一个实用的检查方法是在编码后计算并比较逻辑哈密顿量中不同来源的系数绝对值大小。4.4 实验四ALM 的“理想与现实”目标 探究 ALM惩罚项扰动在次要嵌入前后的效果差异。实验设计 使用两个小型 QAP 实例nug5, tai5a。我们引入扰动ϵ将约束Σ x_{ij} 1的惩罚项改为λ (Σ x_{ij} - 1 - ϵ)^2。在ϵ从 0 到 0.5 的范围内进行测试。实验分两步无次要嵌入模拟退火 SA 作为基线验证 ALM 在理想条件下的效果。有次要嵌入量子退火 QA 在真实硬件流程中测试。结果与分析SA 结果理想情况 与理论预期一致。当施加正扰动ϵ 0时可以用更小的惩罚系数λ达到与ϵ0时相近甚至更高的可行性率。同时在可行性得以维持的情况下更小的λ带来了更好的目标函数值。这证明了 ALM 在逻辑层面的有效性。QA 结果实际情况 出现了戏剧性的反转。在次要嵌入后扰动ϵ不仅没有帮助降低所需的λ反而导致可行性率几乎单调下降。在相同的λ下ϵ越大得到的可行解越少。目标函数值也未因扰动而改善。问题排查与根源分析 为了区分是量子退火器本身的问题还是次要嵌入导致的问题我们增加了一组对照实验使用 SA 来求解经过次要嵌入后的物理哈密顿量。结果与量子退火的结果高度相似。这说明性能下降的根源在于次要嵌入过程本身。我们的推断 次要嵌入改变了问题的局部连接结构。惩罚项(g(σ)-ϵ)^2在逻辑层面是一个全局性的约束。但在嵌入后这个约束被“打散”并分配到了许多局部的链间耦合上。扰动ϵ可能微妙地改变了这些局部相互作用的平衡使得链在演化过程中更容易断裂或者使得满足扰动后约束的低能量态在嵌入后的能量景观中不再占优。这揭示了算法层技巧与硬件底层实现之间存在复杂的相互作用在逻辑层面有效的优化经过硬件映射后可能会失效甚至起反作用。5. 总结、经验与未来展望通过这一系列在真实量子退火硬件上进行的、严格考虑次要嵌入影响的实验我们得到了几个清晰且具有实践指导意义的结论磁场系数缩减通常非必需 次要嵌入过程天然地分摊了逻辑磁场系数。在绝大多数实际QUBO问题中物理磁场系数在缩放后不会大于耦合系数。因此研发新的系数缩减方法时可以优先考虑降低耦合系数即使这可能以增大磁场系数为代价。IEM 是可靠的选择但需谨慎使用 交互扩展方法能有效降低逻辑耦合系数并传导至物理链强度从而提升采样质量。关键是要找到系数缩减与变量增加之间的最佳平衡点无脑追求最小动态范围会导致问题规模膨胀反而损害性能。BCE 效果高度依赖于问题 对于由整数变量平方项主导系数动态范围的简单问题BCE 效果显著。但对于像 MKP 这样的实际问题其他交互项可能成为主导导致 BCE 效果限。在使用 BCE 前务必对问题哈密顿量的系数构成进行剖面分析。ALM 在硬件层面可能失效 增广拉格朗日法或惩罚项扰动在逻辑层面是有效的但次要嵌入可能会破坏其作用机制。这给我们的警示是任何在经典模拟或逻辑层面验证有效的预处理技巧都必须放到完整的硬件流程包含次要嵌入中重新验证。给实践者的建议诊断先行 在尝试任何系数缩减之前先对你的问题执行一次完整的嵌入流程分析物理哈密顿量的缩放因子s_̃h和s_̃J。如果s_̃h明显小于s_̃J那么你的优化重点就应该放在耦合项上。链强度是关键观测指标 评估一个系数缩减方法是否有效不能只看逻辑系数的变化一定要观察最优链强度是否随之成比例下降。如果链强度纹丝不动那么解质量大概率也不会改善。从 IEM 开始尝试 如果你的问题动态范围很大且大系数散布在多个耦合项中IEM 是一个相对稳妥的起点。通过网格搜索寻找一个合适的系数上限M。对“魔法”方法保持怀疑 像 ALM 这样参数敏感、机制复杂的方法在应用到真实硬件前务必用你的具体问题实例在嵌入前后都做充分的测试。不要假设在 SA 上有效的技巧在 QA 上一定有效。未来可能的方向 本次研究也开辟了一些新的思考路径开发嵌入感知的系数缩减方法 既然次要嵌入会改变系数分布能否在设计缩减方法时就考虑嵌入的特性例如能否在嵌入算法中主动将大系数项分配到更长的链上以利用分摊效应自然缩减它探索非基态保持的启发式方法 我们目前的评估框架并不要求缩减方法严格保持基态。未来可以探索那些可能轻微改变解空间但能极大降低动态范围的启发式方法并在我们的框架下量化其“实用价值”——即用解质量的微小损失换取成功率的巨大提升是否值得。系数缩减与纠错编码的结合 量子退火纠错码需要消耗大量额外比特。能否将系数缩减作为减少 QAC 开销的一种预处理或者在存在 QAC 的情况下系数缩减的收益是否会发生变化量子退火硬件仍在快速发展精度在不断提升但噪声和限制短期内不会消失。理解并规避硬件精度的限制通过巧妙的预处理提升有用信息的信噪比是将量子优势从理论推向实践不可或缺的一环。希望本文的探索和发现能为你在量子退火的实际应用之路上提供一些切实的参考和避坑指南。
