⚛️ quantum physics

Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem

该论文提出了一种结合预处理与动态生成子回路消除约束的迭代框架，用于求解旅行商问题，并通过实验验证了该框架在经典、直接量子及混合量子优化方法中均能显著减小模型规模并提升计算性能。

原作者： Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

发布于 2026-04-23

📖 1 分钟阅读🧠 深度阅读

原作者： Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

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

这篇论文讲述了一个关于**“如何用最聪明的方法让旅行商跑遍所有城市并回家”**的故事。

想象一下，你是一位旅行商（Traveling Salesman），你的任务是去拜访 30 个不同的城市，每个城市只去一次，最后回到起点，而且你要花最少的路费。这听起来很简单，对吧？但实际上，随着城市数量的增加，可能的路线数量会像爆炸的宇宙一样瞬间变得无穷无尽，连超级计算机都算不过来。

这篇论文的作者（来自意大利的三位研究者）提出了一套**“组合拳”，试图用经典计算机和新兴的量子计算机**联手来解决这个难题。

为了让你更容易理解，我们可以把这个问题想象成**“在迷宫里找最短路径”**。

1. 核心难题：迷宫里的“死胡同”（子回路）

在数学上，旅行商问题有一个巨大的麻烦：如果你只是简单地规定“每个城市去一次”，计算机可能会给你画出一个**“子迷宫”**。

比喻：想象你要去 5 个城市。计算机可能会给你一条路线：先去 A、B、C 转一圈，然后去 D、E 转一圈，最后把这两圈连起来。但这不符合规则，因为你不能中途“断片”或者走两个互不相连的小圈。
数学术语：这叫“子回路消除约束”（Subtour Elimination Constraints）。
问题所在：为了防止这些“死胡同”，你需要给计算机写无数条规则。城市越多，规则的数量就像指数级爆炸（2 的 N 次方）。如果要把所有规则都写进电脑里，哪怕只有 20 个城市，规则书也会厚得像一座山，电脑根本翻不完。

2. 作者的解决方案：两个“魔法道具”

为了解决这个“规则太多”的问题，作者用了两个聪明的策略：

道具一：智能剪枝（CAF 预处理）—— “只带必要的地图”

做法：在开始找路之前，先看看地图。如果两个城市之间隔着十万八千里，而且中间有更近的路，那这条“远路”肯定不是最优解。
比喻：就像你要去旅行，你先把那些明显绕远、不可能走的路线从地图上撕掉。
效果：这样，计算机需要处理的“候选路线”就大大减少了，就像把一张巨大的世界地图缩小成了你所在城市的局部地图。

道具二：切蛋糕法（CPA 切割平面法）—— “边做边改”

做法：不要一开始就把所有规则（防止死胡同的规则）都写进去。先让计算机随便跑，如果它跑出了一个“死胡同”（比如 A-B-C-A 的小圈），这时候再告诉它：“嘿，这个圈不行，加一条规则禁止它！”然后让它再跑。
比喻：这就像雕刻。你不需要一开始就在一块大石头上刻出所有细节。你先大概刻个形状，发现哪里多了一块（死胡同），就切掉那一块（加一条约束），再切，直到形状完美。
效果：计算机不需要处理那本“厚得像山”的规则书，它只需要处理当前真正需要的那几条规则。

3. 两种“引擎”的较量

作者用这套方法，分别测试了两种“引擎”：

A. 经典计算机引擎（传统方法）

结果：非常成功！
比喻：就像用普通汽车跑长途。虽然车普通，但因为路线被简化了（撕掉了远路），而且不需要背所有规则（边跑边改），它跑得飞快。即使是 45 个城市，也能在几秒钟内算出完美路线。

B. 量子计算机引擎（D-Wave 量子退火）

这是论文最精彩的部分。量子计算机就像**“平行宇宙探险家”**，它能同时尝试无数条路。但它的“内存”很小，而且容易迷路。

直接运行（Direct QPU）：
- 情况：把问题直接扔给量子计算机。
- 结果：就像让一个只有 8 个房间的小旅馆（量子芯片）去住 30 个人。人太多，房间不够，或者规则太复杂，它经常算不出结果，或者算出错误的“死胡同”。
- 改进：用了作者的“剪枝”和“切蛋糕”法后，量子计算机能处理的城市数量从 8 个提升到了 12 个，而且算得准多了。
混合运行（Hybrid Solver）：
- 情况：这是**“人机协作”**模式。
- 比喻：想象一个老练的向导（经典计算机）带着一个拥有超能力的探险家（量子计算机）。
  - 向导负责处理大局，把复杂的问题拆解，过滤掉没用的路。
  - 探险家负责在剩下的关键路段里，利用量子力学的“隧道效应”瞬间找到捷径。
  - 如果探险家走错了（出现死胡同），向导立刻纠正，并让探险家重新尝试。
- 结果：大获全胜！ 这种混合模式成功解决了30 个城市的难题，并且算出的路线几乎是最优的（误差只有 1%）。

4. 总结与启示

这篇论文告诉我们：

不要硬碰硬：面对像旅行商问题这样复杂的难题，直接把所有规则扔给量子计算机是行不通的（就像不能把大象塞进冰箱）。
预处理是关键：先通过“智能剪枝”把问题变小，再通过“边做边改”的策略动态调整，能让量子计算机发挥最大威力。
未来是混合的：目前，“经典计算机 + 量子计算机”的混合模式是解决这类难题的最强组合。它既利用了经典计算机的稳健，又利用了量子计算机的爆发力。

一句话总结：
作者通过**“先删减无用路线”和“发现错误再修正”**这两招，成功地把一个让超级计算机都头疼的数学难题，变成了量子计算机也能轻松应对的任务，为未来量子计算解决现实世界问题（如物流、交通规划）铺平了道路。

这是一份关于论文《通过量子优化切割平面法求解旅行商问题》（Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem）的详细技术总结。

1. 研究背景与问题定义

核心问题：
旅行商问题（TSP）是组合优化中经典的 NP-hard 问题，旨在寻找访问所有城市恰好一次并返回起点的最短路径。
主要挑战：
TSP 的整数线性规划（ILP）模型中，为了保证解是一个单一的哈密顿回路（即避免形成多个不相交的子回路），需要引入大量的子回路消除约束（Subtour Elimination Constraints, SEC）。

约束数量随城市数量 $n$ 呈指数级增长（ $O(2^n)$ ）。
在传统的完全公式化（Complete ILP, CILP）中，显式包含所有约束会导致模型规模过大，即使对于中等规模的问题也无法求解。
在量子优化（特别是量子退火，QA）中，由于量子处理单元（QPU）的量子比特数量有限且连接性受限，这种指数级增长的约束使得直接编码变得极其困难，甚至不可行。

2. 方法论

本文提出了一种混合框架，结合了经典运筹学技术与量子优化方法，旨在解决上述可扩展性问题。主要包含以下三个核心策略：

A. 切割平面法（Cutting-Plane Approach, CPA）

这是本文的核心创新点，首次将迭代式的“懒惰约束生成”（Lazy Constraint Generation）引入到量子退火框架中。

原理： 初始模型仅包含度数约束（每个城市进出一次），不包含子回路消除约束。
流程：
1. 求解松弛后的模型。
2. 检查解中是否存在子回路（Subtours）。
3. 如果存在，仅针对检测到的子回路生成并添加相应的消除约束（即“切割”）。
4. 重复上述过程，直到找到不含子回路的单一回路。
优势： 避免了预先构建庞大的约束集，仅在优化过程中动态添加必要的约束，显著减小了模型规模。

B. 基于成本的弧过滤预处理（Cost-based Arc Filtering, CAF）

原理： 在求解前，根据城市间的距离成本，预先剔除那些不可能属于最优解的弧（边）。
策略： 对每个节点，仅保留成本最低的若干条出边（最近邻）。
优势： 减少了决策变量的数量，降低了图的密度，同时保留了哈密顿回路存在的可能性。

C. 量子优化实现路径

研究对比了两种量子求解路径：

直接量子执行（Direct QPU）：
- 将问题转化为**二次无约束二值优化（QUBO）**模型。
- 所有约束（包括度数约束和动态生成的子回路约束）均通过惩罚项（Penalty Terms）融入目标函数。
- 直接在 D-Wave 量子处理单元上运行。
混合量子 - 经典求解（Hybrid Quantum-Classical）：
- 使用约束二次模型（CQM），允许显式地表示线性或二次约束，无需将其全部转化为惩罚项。
- 利用 D-Wave 的混合求解器（LeapCQMHybrid），结合经典启发式算法（如局部搜索、模拟退火）与量子退火资源。
- 经典模块负责大规模探索，量子模块负责引导式的精细化搜索。

3. 关键贡献

首次应用迭代切割平面法于量子退火框架： 证明了通过动态生成子回路约束，可以显著改善 TSP 在量子硬件上的可扩展性和求解性能。
模型压缩策略的组合： 将 CAF 预处理（减少变量）与 CPA（减少约束）相结合，极大地压缩了问题规模，使其适应当前量子硬件的限制。
对比分析： 系统比较了经典 ILP、直接 QPU 执行（QUBO）和混合求解器（CQM）在处理 TSP 时的性能差异，揭示了不同建模方式对量子求解效果的影响。
基准测试突破： 在标准 TSPLIB 基准测试中，利用混合方法成功求解了节点数高达 30 的实例，这在同类量子优化文献中是首次。

4. 实验结果

实验基于 TSPLIB 中的 berlin52 等标准数据集，使用 D-Wave Advantage2 系统和 Gurobi 求解器进行对比。

A. 模型复杂度分析

CAF 效果： 平均减少了约 26%-32% 的决策变量（随问题规模增大效果更明显）。
CPA 效果： 相比完全公式化（CILP），约束数量减少了 95% 以上，对于大尺寸实例甚至接近 100% 的减少。
结论： 两种策略互补，极大地简化了优化模型。

B. 经典优化结果

CILP： 仅能处理小规模实例（ $V \le 20$ ），随着规模增加，构建模型和求解时间呈指数级爆炸。
CPA + CAF： 能够轻松处理 $V=45$ 的实例，求解时间仅为零点几秒，且始终获得最优解（Gap=0%）。

C. 量子优化结果

直接 QPU (QUBO)：
- CILP 模式： 仅 $V=5$ 时可行， $V \ge 6$ 时无法找到可行解，因为约束过多导致 QUBO 模型过于稠密。
- CPA 模式： 表现显著优于 CILP。在 $V \le 8$ 时能获得 100% 可行性和最优解； $V=9, 10$ 时可行性下降（40%），但优于直接编码。 $V \ge 11$ 时受限于硬件，难以找到可行解。
- 结论： 动态添加约束显著提高了直接量子求解的鲁棒性，但硬件限制仍是瓶颈。
混合量子 - 经典 (CQM)：
- 表现优异： 在 $V \le 25$ 的所有实例中均获得了0% 的优化间隙（即最优解）。
- 大尺寸表现： 在 $V=30$ 时，优化间隙仅为 1%，且计算时间可控（约 140 秒）。
- 结论： 混合方法是目前利用量子技术解决组合优化问题最有效、可扩展性最强的策略。

5. 研究意义与结论

理论意义： 证明了通过经典的运筹学技巧（切割平面法）与量子计算相结合，可以有效克服当前量子硬件在约束编码和规模上的局限性。
实践意义： 为 TSP 及类似的路径规划问题提供了可行的量子求解方案。研究表明，混合量子 - 经典方法（Hybrid Quantum-Classical）比纯量子方法（Direct QPU）更具优势，能够解决更大规模的实际问题。
未来展望： 随着量子硬件的进步（更多量子比特、更好的连接性）以及编码策略的优化（如自适应参数调整、分解技术），纯量子方法有望进一步提升竞争力。

总结： 该论文通过引入“切割平面”和“弧过滤”策略，成功地将 TSP 问题转化为适合当前量子退火硬件处理的形式。实验表明，这种混合框架不仅显著提升了经典求解器的效率，更重要的是，它使得量子优化方法能够处理以前无法解决的中等规模 TSP 实例，填补了理论量子优势与实际应用之间的鸿沟。