Quantum optimization beyond QUBO for industrial logistics and scheduling

本文研究了工业物流与调度领域的高阶无约束二进制优化（HUBO）公式，表明尽管与标准 QUBO 模型相比，它们能提供更紧凑的二进制编码并减少量子比特需求，但其受限于电路深度增加而在当前硬件上的实际部署受到制约，这表明混合量子 - 经典工作流和早期容错系统是最可行的前进路径。

要点

想象一下，你正在尝试解决一个庞大而复杂的拼图。在工业物流的世界里——比如规划如何配送成千上万个包裹，或者如何在工厂流水线上组装汽车——这种拼图极其困难。长期以来，科学家们一直试图利用量子计算机来比传统计算机更快地解决这些难题。

然而，这里有一个陷阱：当今大多数量子计算机就像试图将“方榫”塞进“圆孔”里。它们被设计用来解决用一种特定且简单的语言编写的难题，即QUBO（二次无约束二进制优化）。可以把 QUBO 想象成一种语言，你只能一次描述两个事物之间的关系（例如：“如果 A 在这里，那么 B 必须在那里”）。

但现实世界的问题往往是混乱的。它们通常涉及复杂的规则，其中三个、四个甚至更多事物同时相互依赖。试图将这些复杂规则强行塞进简单的“一次两个”的 QUBO 语言中，就像只通过谈论成对的音符来描述一部交响乐。这虽然可行，但你必须将音乐拆解得如此彻底，以至于拼图变得巨大无比，所需的“碎片”（量子比特）数量超过了量子计算机所能提供的数量。

新策略：使用“原生”语言

本文提出了一种不同的策略。研究人员建议不要将复杂问题强行塞入简单的 QUBO 语言，而是使用HUBO（高阶无约束二进制优化）。

类比：
想象你在收拾行李箱。

• QUBO 方式： 你必须为每一对物品写一张便条，以查看它们是否合得来。如果你有 100 件物品，你就得写成千上万张便条。这占据了大量空间（内存/量子比特）。
• HUBO 方式： 你只需写一张稍显复杂的便条，上面写着：“这五件物品完美契合。”这要紧凑得多。描述同一个行李箱所需的便条（量子比特）要少得多。

研究人员将这种"HUBO"方法应用到了三个现实世界的工业场景中：

1. 防风衣与冲浪者（QUEST）： 匹配在高速公路上行驶的汽车，使一辆车能跟在另一辆车后面行驶以节省燃料。
2. 送货卡车（CVRP）： 规划拥有有限载货空间的车队的最佳路线，以便向众多客户交付货物。
3. 汽车装配线： 决定具有不同配置（如天窗、真皮座椅）的汽车应以何种顺序进入流水线，以避免瓶颈。

权衡：节省空间与建造高塔

本文强调了一个关键的权衡，就像在宽而矮的建筑与高而窄的摩天大楼之间做出选择。

• 优势（更少的量子比特）： 通过使用 HUBO，研究人员成功缩小了问题的规模。他们表示该问题所需的“量子位”（量子比特）数量显著减少。这非常好，因为目前的量子计算机非常小，拥有的量子比特很少。
• 代价（更深的电路）： 然而，为了让那张“单一的复杂便条”生效，量子计算机必须执行更为复杂的“舞蹈”。用量子术语来说，这意味着“电路深度”（计算机必须执行的步骤数量）变得更深。

隐喻：
将量子计算机想象成走钢丝的人。

• QUBO 是一条短而宽的钢丝。在上面保持平衡很容易，但你需要一根非常长的绳子（许多量子比特）才能到达另一端。
• HUBO 是一条非常短而窄的钢丝。你只需要很少的绳子（很少的量子比特），但要在上面保持平衡极其困难，因为它需要复杂、高速的动作（深层电路）。

结果说明了什么

研究人员利用模拟和经典计算机测试了这些想法，以观察 HUBO 方法的效果。

1. 它行得通（理论上）： 对于小规模问题，HUBO 方法成功找到了最佳解决方案。它证明了你可以用更少的“成分”（量子比特）更高效地描述这些复杂的物流问题。
2. 硬件瓶颈： 问题在于当前的量子计算机是“有噪声的”。它们就像试图在飓风中保持平衡的走钢丝者。由于 HUBO 方法需要更长、更复杂的步骤序列（更深的电路），噪声会导致计算机在完成拼图之前就失去平衡。
3. 结论：
   • 今天（噪声时代）： “高塔”（HUBO）对于当前的硬件来说太不稳定了。“宽建筑”（QUBO）实际上更容易在当下构建，尽管它占用更多空间。
   • 明天（容错时代）： 本文指出，一旦我们拥有更好的、经过纠错的量子计算机（即“容错”阶段），HUBO 方法很可能会胜出。这些未来的机器将足够稳定，能够处理 HUBO 所需的复杂深层电路，从而让我们用更少的量子比特解决更大的问题。

混合解决方案

既然我们无法等待完美的未来计算机，本文建议在近期内采用一种“混合”方法。不要试图一次性在量子计算机上解决整个巨大的拼图，而是将拼图分解为小的、可管理的部分。我们使用经典计算机来处理大局和简单的部分，而只将微小的、困难的部分发送给量子计算机进行优化。

总结：
本文认为，虽然“紧凑”的 HUBO 语言是描述复杂工业物流最高效的方式，但目前的量子计算机过于脆弱，无法处理其所需的复杂性。我们需要等待更好的硬件，或者结合经典计算与量子计算，才能使这种强大的方法变得实用。

技术摘要

技术摘要：超越 QUBO 的量子优化在工业物流与调度中的应用

问题陈述
工业调度与运输路径规划问题日益复杂，往往具有自然的数学结构，导致其形成高阶无约束二进制优化（HUBO）公式，而非纯粹的二次型公式。尽管量子优化领域主要集中于二次无约束二进制优化（QUBO），因其能原生映射到伊辛哈密顿量（Ising Hamiltonians）且与当前量子退火机兼容，但这种聚焦带来了显著局限。通过辅助变量将 HUBO 问题降阶为 QUBO，往往会膨胀问题规模（量子比特数量），掩盖关键依赖关系，并无法忠实反映复杂的操作约束。相反，虽然像量子近似优化算法（QAOA）这样的数字量子算法理论上能够处理高阶相互作用，但在含噪硬件上的近期实现往往因相互作用阶数增加而受限于电路深度。本文探讨了 HUBO 公式的表示紧凑性与其在当前及新兴量子硬件上的实现成本之间的权衡。

方法论
作者提出并分析了三个代表性工业用例的 HUBO 公式：

1. QUEST（量子增强共享交通）： 一个车辆匹配问题，将“破风者”（breakers）与“冲浪者”（surfers）配对，以最小化空气阻力及时间/速度不匹配。
2. CVRP（带容量约束的车辆路径问题）： 一个带有容量约束的车队路径规划问题，是旅行商问题（TSP）的扩展。
3. 汽车装配调度： 一个涉及装配线上间隙、分组和存储车道约束的汽车排序问题。

针对每个用例，作者利用紧凑二进制编码（变量呈对数级扩展）而非标准独热编码（变量呈线性级扩展），将问题重构为 HUBO。这些公式使用经典求解器（包括模拟退火 SA 和模因禁忌搜索 MTS）进行验证，并与整数线性规划（ILP）及暴力求解方案进行基准测试。

为了评估量子可行性，作者采用了**偏置场数字化反绝热量子优化（BF-DCQO）**算法。该协议通过引入迭代反馈机制扩展了标准 DCQO，利用源自先前测量结果的纵向偏置场引导系统趋向更低能量构型。作者在各种硬件连接假设（全连接、重六边形、方格晶格）和噪声模型下，估算了资源需求（量子比特数量、双量子比特门数量、电路深度）及电路保真度。

主要贡献

• HUBO 模型的构建： 本文提供了 QUEST、CVRP 和汽车调度的明确 HUBO 公式，展示了紧凑二进制编码如何将二进制变量数量从 $O(N)$ 或 $O(N^2)$ 减少至 $O(N \log N)$。
• 权衡分析： 该工作系统地突出了核心权衡：HUBO 公式显著降低了量子比特需求（量子比特扩展），但引入了高阶相互作用项，这需要更深的电路和更多的双量子比特门。
• 资源与可扩展性分析： 作者提供了 BF-DCQO 的电路保真度和运行时间的详细估算。他们证明，虽然 HUBO 减少了量子比特占用，但电路保真度随双量子比特门数量增加而呈指数衰减，这对当前含噪中等规模量子（NISQ）设备构成了关键瓶颈。
• 混合工作流提案： 对于全量子执行不可行的大规模实例（如汽车调度），本文提出并评估了一种混合滚动时域工作流。该方法将全局问题分解为可由经典或近期量子求解器解决的局部子问题，同时保留完整目标函数的高阶结构。

结果

• QUEST 和 CVRP 验证： 对于小规模实例（QUEST 最多 6 个破风者/冲浪者，以及小规模 CVRP 实例），BF-DCQO 模拟恢复了最优解，验证了 HUBO 编码的有效性。然而，随着问题规模增大，BF-DCQO 的近似比率下降速度快于在二次化 HUBO 上的经典模拟退火，这与电路复杂度的迅速增加一致。
• 硬件限制： 分析显示，对于当前硬件（如 IBM 的重六边形或方格晶格），QUBO 编码通常更具可行性，尽管需要更多量子比特，但其双量子比特门数量较低。HUBO 公式仅在具有全连接架构（如离子阱）的硬件上在门数量方面才具有竞争力，即便如此，由于相干时间和误差累积，其仍仅限于非常小的实例（例如 CVRP 中的 4 个客户）。
• 可扩展性限制： 对于一个具有代表性的大规模 CVRP 实例（100 个客户），作者估算，若要忠实地实现 DCQO 电路，平均双量子比特门错误率需低于 $10^{-10}$，这一水平仅在由量子纠错实现的逻辑量子比特 regime 中才能达到。
• 调度性能： 在汽车调度案例中，使用经典求解器（MTS 和 ILP）对 HUBO 公式进行了基准测试。MTS 有效减少了先进先出（FIFO）违规，但随着问题规模增大，在处理高阶分组约束时显得力不从心。使用 SA 的混合滚动时域方法在减少局部和全局违规方面提供了平衡的改善。

意义与主张
本文谦逊地主张，其主要贡献并非在工业规模实例上展示量子优势，而是阐明何时高阶公式能提供有意义的表示优势，以及这种优势如何受量子资源需求的制约。

作者得出结论：

1. HUBO 与 QUBO： HUBO 公式提供了更优的量子比特扩展，使其在早期容错设置中（量子比特数量有限但门保真度高）可能比 QUBO 更具吸引力。
2. 当前局限： 在当前 NISQ 硬件上的实际实施受限于门保真度、相干时间和电路深度。HUBO 增加的双量子比特门需求往往超过了当前设备上减少量子比特数量所带来的益处。
3. 未来路径： 这些公式实际应用最可能的场景是顺序混合量子 - 经典工作流。在这种范式中，量子过程作为主要经典优化流水线中局部子问题的细化步骤。这种方法利用了 HUBO 有利的量子比特扩展，同时缓解了端到端量子优化相关的不可行运行时间和误差累积，即使在早期容错 regime 中也是如此。

该工作强调，量子优化在工业界的可行性取决于将问题结构与硬件能力相协调，表明混合策略对于弥合理论 HUBO 优势与实际实施之间的差距至关重要。