⚛️ quantum physics

Minimum Bisection Problem: Machine Learning-Based Penalty Parameter Tuning for Optimization on Quantum Annealers

本文提出了一种基于机器学习的框架，该框架利用梯度提升回归器来自动调节量子退火机上最小二分问题的惩罚参数，以预测有效的惩罚区间，并证明了其在生成具有更低切割值的平衡划分方面，其性能优于像 Metis 这样的经典启发式算法。

原作者： Renáta Rusnáková, Martin Chovanec, Juraj Gazda

发布于 2026-08-25

📖 1 分钟阅读🧠 深度阅读

原作者： Renáta Rusnáková, Martin Chovanec, Juraj Gazda

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个由道路、计算机或输电线路组成的庞大网络，它们以复杂的网状结构相互连接。为了高效管理这样的系统，工程师通常需要将其分为两个相等的两半，在确保两个新组规模平衡的同时，尽可能减少它们之间的连接。这项被称为“最小二分问题”（minimum bisection problem）的任务是计算机科学中的一个经典挑战。它对于从微芯片设计到数据中心组织等各个领域都至关重要，然而寻找完美的分割方式却极其困难。随着网络的增长，可能的切割方式会呈爆炸式增长，使得传统计算机几乎不可能检查所有选项。近年来，一种被称为量子退火机（quantum annealer）的新型计算机应运而生，成为解决这类难题的潜在工具。这些机器并不像标准笔记本电脑那样逐步计算答案，而是利用量子物理学的奇特规则同时探索许多可能性，寻求能量最低的状态，而这个状态正对应着最佳解决方案。然而，为了让这些量子机器正常工作，必须将问题转化为特定的数学格式，而这一转化过程中的一个关键部分涉及到一个“惩罚值”（penalty value）。这个数值就像一条严格的规则，迫使机器保持两半的大小相等。如果惩罚值太弱，机器就会忽略规则并产生一个不平衡且无用的结果；如果惩罚值太强，机器会过度专注于规则，从而忘记了最小化实际的切割量，导致产生较差的解。为这个惩罚值寻找平衡点，在传统上一直是一个靠猜测和人工反复试验的过程。

来自斯洛伐克科希策技术大学的一个研究小组开发了一种新的方法来解决这个“猜谜游戏”。他们不再要求人类为每个新网络调整惩罚值，而是教会了一个计算机程序自动预测完美设置的方法。研究人员首先生成了数百个随机网络图，范围从小型集群到拥有数千个节点的巨型网络。对于每张图谱，他们在 D-Wave Systems 提供的量子系统上进行了实验，测试了广泛的惩罚值，以观察哪些值能产生最好的结果。他们发现，理想的惩罚值并非随机，而是遵循基于网络规模和节点连接密度的某种模式。利用这些数据，他们训练了两个机器学习模型，具体是一种被称为“梯度提升回归器”（gradient boosting regressor）的算法，作为预测器。这些模型学会了观察一个新的、未见过的网络，统计其节点数量，测量其密度，并计算出一个粗略的初始估计，然后输出一个极有可能表现最佳的精确惩罚值范围。

当研究人员在 126 个全新的网络上测试这种新方法时，结果令人瞩目。在每一个案例中，该机器学习系统都引导量子求解器找到了一个完美的平衡分割。此外，这些分割的质量优于目前现有的最佳传统软件工具。那些依赖成熟经典算法的传统软件，在约一半的测试案例中未能产生平衡的分割。即使在成功实现分组平衡的情况下，它所必须切断的连接数量也始终高于量子系统在经过机器学习调优惩小心值后所实现的连接数。研究人员发现，这种改进在他们测试的所有规模中都成立，从 100 个节点的微型网络到高达 4,000 个节点的巨型网络。这种机器学习方法本质上消除了手动测试不同值的繁琐过程，让量子系统能够全身心地投入到寻找最优解中。

该研究还考察了这种方法在实际量子硬件上（而非结合了经典与量子处理的混合系统）的表现。对于较小的网络，直接使用量子硬件展现出了潜力，通常优于传统方法，但在处理某些图中极其密集的连接时仍显吃力。研究人员指出，他们方法的成功很大程度上取决于用于训练的特定随机网络类型。虽然该方法在这些合成图谱上表现完美，但他们警告说，在将其应用于现实世界网络（如真实的道路地图或社交网络）之前，需要对其进行重新训练和测试。他们还指出，由于当前量子硬件的局限性，对于非常大的问题，混合系统仍然是最实用的工具，因为它可以承担准备问题的重任，同时让量子部分负责搜索解决方案。

最终，这项工作证明了机器学习可以作为复杂优化问题与新兴量子技术之间的重要桥梁。通过自动化关键参数的调优，研究人员使量子退火过程变得更加可靠和高效。他们的发现表明，随着量子计算机的不断演进，将它们与智能的数据驱动调优系统相结合，对于解决目前经典计算机难以高效处理的现实世界问题将至关重要。这项研究并非声称解决了所有可能场景下的最小二分问题，但它提供了一个稳健且经过验证的框架，使量子解决方案能够比以往任何时候都更好地发挥作用，将一个曾经需要专家直觉的过程转变为一个可以由训练有素的算法来处理的过程。

技术摘要：基于机器学习的量子退火器最小二分问题惩罚参数调优

问题定义
最小二分问题（Minimum Bisection Problem, MBP）是一个基础的 NP-hard 图划分问题，要求将图的节点划分为两个大小相等的子集，同时使连接这两个子集的边数最小化。虽然 MBP 在并行计算和网络设计中具有应用价值，但通过量子退火解决该问题需要将其表述为二次无约束二进制优化（QUBI）模型。该表述中的一个关键挑战是选择惩罚参数 ( $\lambda$ )，用于强制执行平衡约束（即子集大小相等）。如果 $\lambda$ 过小，求解器会返回违反平衡约束的不可行解；如果 $\lambda$ 过大，惩罚项会主导目标函数，从而掩盖了最小化切割的目标。现有方法依赖于手动调优或静态启发式算法，这些方法往往依赖于特定问题，且在面对变化的图结构时缺乏可靠性。

方法论
作者提出了一种数据驱动的框架，专门用于自动化选择针对量子退火器上 MBP 的 $\lambda$ 。该方法通过四个阶段进行：

理论边界与初始估计：
作者通过分析能量景观，推导出了一个与图相关的初始估计值 ( $\lambda_{est}$ )。他们建立了一个理论下界 ( $\lambda \ge 1$ ) 和一个基于最大节点度数及图规模的实际上界 ( $\lambda \le \min(\Delta(G), n/2 - 1)$ )。初始估计值设定为此区间的中点。该方法仅依赖于可测量的图属性（ $n$ 和 $\Delta(G)$ ），而非图的生成参数，从而确保了对任意输入图的适用性。
经验缩放与校准：
初步实验表明，理论中点值通常需要进一步缩放，特别是在处理较大规模的图时。作者使用 607 个 Erdős–Rényi 图 ( $G(n, p)$ ，规模高达 4000 个节点) 进行了一个校准阶段。他们测试了应用于 $\lambda_{est}$ 的各种乘数 ( $\lambda_{mult}$ )，以确定能够在使用 D-Wave 混合量子-经典求解器 (QA HS) 时，产生有效平衡划分且具有最小切割规模的数值范围。
机器学习预测：
为了消除在候选乘数上进行昂贵的人工搜索的需求，作者训练了两个梯度提升回归器 (GBR) 模型。

输入： 模型接收三个特征：节点数 ( $n$ )、实际图密度 ( $\rho$ ) 以及初始惩罚估计值 ( $\lambda_{est}$ )。
输出： 一个模型预测下界 ( $\lambda_{min}$ )，另一个模型预测有效乘数区间的上界 ( $\lambda_{max}$ )。
最终计算： 最终的惩罚参数计算公式为 $\lambda = \lambda_{est} \times \frac{\lambda_{min} + \lambda_{max}}{2}$ 。

实验评估：
训练好的模型在 126 个独立生成的 Erdős–Rényi 图（规模高达 4000 个节点）上进行了评估，并与经典基准算法进行了对比：Metis（多层划分法）和 Kernighan–Lin（局部细化法）。研究还进行了直接的 QPU 实验（针对规模较小的图， $n \le 100$ ），以评估硬件特定的性能。

核心贡献

针对 MBP 的特定框架： 本文引入了一个结合了基于图的解析估计与机器学习的框架，用于预测有效的惩罚乘数区间，超越了通用的惩罚调优方法。
校准数据集： 作者生成并利用了一个包含 607 个 Erdős–Rényi 图的数据集来训练模型，并在 126 个未见的实例上进行了评估，涵盖了广泛的规模（最高达 4000 个节点）和密度。
性能验证： 研究表明，学习到的惩罚选择使得混合求解器能够在所有评估实例中实现 100% 的有效平衡划分，相比初始的启发式估计有了显著提升。

结果

可行性： 在采用的实验设置下，经 GBR 预测的惩罚参数使 D-Wave 混合求解器能够为所有 126 个评估实例返回平衡划分。
解质量： 使用预测惩罚项的混合求解器在 100% 的评估案例中实现了比 Metis 更低的切割值（更少的切割边）。使用 Wilcoxon 符号秩检验进行的统计分析证实，这些差异具有显著性 ( $p < 0.001$ )。
直接 QPU 性能： 对于小规模图 ( $n \le 100$ )，在 $n \ge 80$ 时，QPU 在多数实例中表现优于 Metis，但在规模较小的图中表现不一，这可能是由于模型主要针对较大的实例进行训练。
模型准确度： 用于预测上界 ( $\lambda_{max}$ ) 的 GBR 模型达到了 0.9028 的高 $R^2$ 分数。由于目标值的方差较低，预测下界 ( $\lambda_{min}$ ) 的模型 $R^2$ 较低 (0.4489)，但保持了较低的绝对误差 (MAE 0.0124)。

意义与声明
本文声称其主要贡献不在于自动惩罚调优这一通用概念，而在于一个特定的、聚焦于 MBP 的框架，该框架能从基础图属性中推导出经验有效的惩罚范围。作者断言，这种数据驱动的方法提高了 MBP 在量子退火器上的可靠性和解质量，减少了重复进行人工参数测试的需求。

本研究指出，其结果是针对所使用的 Erdős–Rényi 图分布和 D-Wave 混合求解器配置特定的。作者并未声称在所有经典算法面前具有普遍的优越性（例如，他们承认 Metis 在纯运行时间方面明显更快），但认为所提出的调优使量子方法在解质量方面具有竞争力，同时确保了可行性。未来的工作方向包括将该框架扩展到其他图族、真实世界基准测试以及 $k$ -划分问题。

类似论文