Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

技术摘要：用于求解混合整数线性规划（MILP）的混合量子-经典端到端流水线

问题陈述
混合整数线性规划（MILP）问题是物流和供应链管理等行业中高影响力决策的核心，但由于其组合性质，计算挑战巨大。虽然诸如 Benders 分解（BD）之类的分解技术被广泛用于解决大规模 MILP 问题（通过将问题分为主问题 MP 和子问题 SP），但这些技术往往面临收敛缓慢的问题。这种收敛性在很大程度上取决于向主问题中添加具有信息量的“割”（cuts，即约束条件）的选择。此前，Paterakis [1] 提出使用量子退火来解决割选择步骤——该步骤被建模为最小集合覆盖问题（Minimum Set Cover problem）——以加速这一过程。然而，量子退火需要昂贵的次级嵌入（minor-embedding）程序，这在扩展规模时会引入显著的开销。

方法论
本文提出了一种端到端的混合量子-经典优化框架，该框架扩展了“多解多割”（Multiple Cuts via Multiple Solutions, MCMS）Benders 分解方法。其核心创新在于使用基于门（gate-based）的量子近似优化算法（QAOA）实现来取代原有的量子退火步骤。

该框架运行如下：

1. MCMS Benders 分解： 算法在每次迭代中生成多个候选解，通过并行求解多个子问题来产生候选割池。
2. 作为 QUBO 的割选择： 为了防止主问题因过多的割而变得计算过于昂贵，系统会选择一个具有信息量的割子集。这被建模为一个最小集合覆盖问题，随后被映射为一个二次无约束二进制优化（QUBO）实例。
3. QAOA 集成： 与之前的退火法不同，本框架使用 QAOA 来求解该 QUBO。该流水线与三个不同的求解器对接：
   • Fermioniq 的 Ava： 一个张量网络电路模拟器。
   • MPS-JuliQAOA： 一个基于 Julia 构建的开源矩阵乘积态（MPS）模拟器。
   • IBM Quantum： 直接在超导量子硬件（IBM Eagle 处理器）上执行。
4. 案例研究： 本框架在车辆路径问题（VRP）上进行评估，这是一个经典的物流优化问题。研究利用来自 QOptLib 的标准化基准测试（20 个客户，4 辆车）以及随机生成的玩具实例（5 个客户）来测试流水线的可行性。

主要贡献

• 基于门的扩展： 本文将现有的 HQC-MCMS 框架从量子退火扩展到基于门的量子计算，使其能够在张量网络模拟器和超导量子处理器上运行。
• 端到端实现： 作者成功展示了一个功能完备的流水线，该流水线将 QAOA 子程序集成到经典的 Benders 分解循环中。
• 经验基准测试： 研究针对 VRP 实例，对不同求解器后端（经典 Cbc、MPS-JuliQAOA、Fermioniq 和 IBM Quantum）的流水线性能进行了对比分析。

结果
实验结果针对当前量子优势在此特定背景下的可行性提供了几个关键见解：

• 经典性能： 在完全经典的设置下（使用 Cbc 进行割选择），流水线成功找到了 20 客户 VRP 实例的可行解，且最优间隙（optimality gap）随迭代次数增加而减小。使用更多子问题的多割（Multi-Cut）方法能在更少的迭代次数内获得可行解。
• 运行时瓶颈： 对经典流水线的分析表明，割选择步骤仅占总迭代时间的极小部分。大部分计算时间都消耗在求解主问题上。
• 量子性能： 当在玩具问题上使用 QAOA 替换割选择步骤（使用 MPS-JuliQAOA）时，总运行时间相比于经典方法显著增加。研究指出，在此规模下，MPS-JuliQAOA 的效率远低于用于最小集合覆盖问题的经典求解器 Cbc。
• QAOA 输出： 在量子硬件和模拟器上的实验表明，对于测试的配置，大多数 QAOA 样本结果是不可行的（即它们无法构成有效的集合覆盖）。虽然较深的电路（$p=3$）比较浅的电路（$p=1$）产生了更多的最优代价样本，但整体表现并未超越经典方法。

意义与主张
论文对该框架的现状给出了审慎的评估。作者明确指出，对于所测试的问题规模和配置，量子优势不太可能实现。其主要原因有两个方面：

1. 割选择步骤（即旨在实现量子加速的部分）在当前的经典 MCMS 流水线中并不是计算瓶颈；主问题的求解占据了主要的运行时间。
2. 针对特定的最小集合覆盖实例，经典求解器（Cbc）的表现远优于 QAOA 实现。

作者强调，虽然该流水线在技术上是可行的，并展示了迈向量子增强优化的可复现步骤，但将集合覆盖问题转化为 QUBO 引入了实质性的开销。他们认为，未来的研究必须侧重于更大规模的基准测试，届时割选择步骤可能会成为更显著的瓶颈，并且更强大的量子处理器（QPU）才可能展现出价值。该研究作为一个经验性的警示分析，强调了目前的量子方法在处理此类实际的中小规模实例时，尚无法为该特定分解步骤提供加速。