QUACOD: Quantum Optimization via Coordinate Descent for Scalable Drone Scheduling

本文介绍了 QUACOD，这是一种可扩展的量子优化方法，它利用坐标下降法将复杂的无人机调度问题分解为可管理的子问题，从而在当前的有限量子比特硬件上实现有效求解，同时在效率和可扩展性方面显著优于现有方法。

要点

想象一下，你是一家庞大配送无人机机队的经理。你有数百个包裹需要投递，但你的无人机有一个限制：它们无法永远飞行。它们需要降落、给电池充电，并装载新的包裹。你的目标简单却棘手：以最快的速度投递每一个包裹，同时确保没有无人机在等待，而其他无人机仍在工作中。

这就是“无人机调度问题”。它就像试图组织一场混乱的舞蹈，每个人的舞步都不同，而你希望当最后一名舞者结束时，音乐也恰好停止。

问题：舞者太多，舞台太小

在现实世界中，为数百架无人机制定完美调度方案对计算机来说是一场噩梦。这是一个极其复杂的数学谜题，甚至世界上最快的超级计算机也难以应对。

最近，科学家们想到：“让我们使用量子计算机吧！”这些是未来派的机器，能够比传统计算机更快地解决某些谜题。然而，有一个限制：目前的量子计算机就像微小而脆弱的乐器。它们只有少量的“量子比特”（量子版本的脑细胞）。试图在它们身上解决庞大的无人机问题，就像试图把整个管弦乐队塞进一个鞋盒里。目前的量子硬件根本不足以一次性处理整个问题。

解决方案：QUACOD（“分块”策略）

这篇论文的作者是 Van-Quang-Huy Nguyen 及其同事，他们提出了一种巧妙的变通方法，称为 QUACOD（基于坐标下降的量子优化）。

将 QUACOD 想象成一位“聪明的项目经理”，他知道量子计算机太小，无法一次性处理整个团队。QUACOD 不是试图同时调度全部 100 架无人机，而是将问题分解成微小、可管理的部分。

以下是其工作原理，使用一个简单的类比：

1. “焦点小组”方法：想象你有一个由 100 架无人机组成的大团队。QUACOD 不会要求量子计算机一次性调度全部 100 架。相反，它会挑选一个小型“焦点小组”——比如，仅 5 架无人机和 10 条路线。
2. 量子冲刺：它仅将这个小组发送给量子计算机。量子计算机迅速找出调度这 5 架无人机的最佳方案。
3. “坐标下降”循环：一旦量子计算机完成，QUACOD 就将这 5 架无人机固定下来。然后，它挑选另一组不同的无人机（也许是另外 5 架），并将它们发送给量子计算机。
4. 重复过程：它不断重复这一过程，反复替换不同的无人机组。每一轮，整体调度都会变得更好一点，就像调谐收音机直到杂音消失一样。

通过将庞大的问题分解为小的“坐标”（即变量小组），QUACOD 使得一台微小的量子计算机能够解决它独自无法处理的巨大问题。

结果：超越竞争对手

该团队将 QUACOD 与之前的最佳方法（称为 QUADRO）进行了测试。以下是他们的发现：

• 速度与效率：QUACOD 找到的调度方案比旧方法完成得更快。
• 可扩展性（重大胜利）：旧方法（QUADRO）只能处理约 11 架无人机。而 QUACOD 使用同样的小型量子“鞋盒”，成功处理了包含55 架无人机（5 倍）和1,000 条路线（35 倍）的问题。
• 硬件效率：他们证明，你不需要一台庞大且完美的量子计算机。如果你采用正确的策略（例如他们那种“硬件高效”的电路设计），就可以使用小型、有“噪声”的量子计算机（即我们今天拥有的那种）。

核心结论

该论文声称，QUACOD 是一座桥梁。它将量子计算的能力转化为当下即可用于现实世界物流问题的工具，即使使用我们目前有限的技术也是如此。它并不承诺解决宇宙中所有的物流问题，但它证明，通过将大问题分解为小片段，我们可以利用当今的小型量子计算机完成此前不可能完成的工作。

简而言之：QUACOD 是一种聪明的策略，它让一台微小的量子计算机能够像巨型计算机一样运作，帮助我们比以往更快、更高效地调度无人机配送。

技术摘要

技术摘要：QUACOD——基于坐标下降的量子优化用于可扩展无人机调度

1. 问题陈述

本文 addressed 无人机调度问题，这是最后一公里物流的关键组成部分，其目标是将预先计算好的路线分配给一组相同的无人机，以最小化整个机队的最大完成时间（$C_{max}$）。

该问题的关键约束和特征包括：

• 电池约束：无人机必须在连续路线之间进行充电，引入不可忽略的充电时间（$c$），这会显著影响总完成时间。
• 组合复杂性：该问题是 NP 难的，与旅行商问题相关，随着路线数量（$n$）和无人机数量（$q$）的增加，解空间呈指数级增长。
• 硬件限制：当前的含噪声中等规模量子（NISQ）设备缺乏编码大规模调度问题所需的量子比特数量，无法直接将其映射到量子退火或变分量子算法（VQA）中，从而阻碍了实际应用。现有的量子方法（如 QUADRO）仅限于非常小的实例（例如，少于 11 架无人机）。

2. 方法论：QUACOD

作者提出了QUACOD（基于坐标下降的量子优化），这是一种混合量子 - 经典框架，旨在严格的量子比特约束下解决大规模调度问题。

A. 问题建模与 QUBO 转换

调度问题最初被建模为在满足分配约束（每条路线恰好分配给一架无人机）和容量约束的前提下最小化 $C_{max}$。为了使其与量子优化兼容，作者将问题转换为**二次无约束二值优化（QUBO）**格式：

1. 约束处理：等式约束（路线分配）被转换为惩罚项并添加到目标函数中。
2. 目标转换：作者没有直接最小化 $C_{max}$，而是利用了一个启发式方法，即观察到最小化各无人机完成时间（$T_j$）与平均完成时间（$T/q$）之间偏差的平方和，能有效最小化 $C_{max}$。这消除了复杂的非等式约束。
3. 最终目标：生成的 QUBO 函数最小化 $T_j$ 的偏差平方和加上未分配路线的惩罚项。

B. QUACOD 算法

为了克服量子比特稀缺的限制，QUACOD 采用了坐标下降优化策略：

• 分解：算法不是同时优化所有 $n \times q$ 个二值变量，而是迭代地选择一小部分路线（$N$）和无人机（$Q$）。
• 变量选择：子集的选择需满足以下条件：
  • 变量数量（$|N| \times |Q|$）不超过可用量子比特数（$m$）。
  • 子集包含完成时间最高的无人机（瓶颈）和完成时间最低的无人机（负载不足），以促进重新分配。
  • 选择确保非平凡解（每架被选中的无人机当前至少分配有一条路线）。
• 量子子程序：选定的子问题使用变分量子本征求解器（VQE）求解，采用硬件高效 ansatz（单层，包含 $R_y$ 旋转和线性 $CZ$ 纠缠）。
• 迭代：未选中的变量被固定，该过程重复直至收敛。

C. 硬件高效 Ansatz

本文采用了一种特定的 VQE ansatz，由两个 $R_y$ 旋转块组成，中间由线性链的 $CZ$ 纠缠门隔开。选择这种设计是因为其与 NISQ 设备的兼容性，以及其能够以单层产生高质量解，避免了与 QAOA 相关的深层电路和高计算成本。

3. 主要贡献

1. 新颖算法：提出了 QUACOD，这是一种混合方法，将高复杂度的无人机调度分解为可由当前量子硬件解决的子问题。
2. 可扩展性：证明了坐标下降可以弥合理论量子优势与实际 NISQ 限制之间的差距，使得解决比先前方法处理规模大得多的问题成为可能。
3. 性能验证：实证证据表明，QUACOD 在解的质量（更低的完成时间）和可扩展性方面均优于最先进的方法（QUADRO）。
4. 硬件效率：验证了硬件高效电路对组合优化的有效性，支持了近期量子部署的可行性。

4. 实验结果

作者使用量子硬件的经典模拟（Qiskit）在两个数据集上评估了 QUACOD：

• 与 QUADRO 的比较（Augerat 数据集）：

  • QUACOD 在六个具有不同无人机数量和路线数量的实例上进行了测试。
  • 结果：QUACOD 始终找到了比 QUADRO 的混合方法和纯量子方法更低的最大完成时间的解。
  • 可扩展性：虽然 QUADRO 无法调度超过 11 架无人机的实例，但 QUACOD 成功处理了多达50 架无人机和 1,000 条路线的实例（是 QUADRO 限制的 5 倍无人机和 35 倍路线）。

• 大规模基准测试（并行机器调度数据集）：

  • 实验在从 200 到 3,000 条路线以及 5 到 100 架无人机的实例上进行。
  • QUACOD 成功解决了大多数大规模实例，仅使用了20 个量子比特进行量子模拟。
  • 局限性：两个最大实例（3,000 条路线，100 架无人机）因存储 QUBO 目标函数中 $O(n^2q^2)$ 项所需的经典内存（RAM）限制而失败，而非量子硬件限制。

5. 意义与主张

本文主张，QUACOD 代表了 NISQ 时代迈向实际量子应用的重要一步，具体体现在：

• 克服资源障碍：它证明了通过利用经典分解策略（坐标下降），可以在有限的量子比特下解决复杂的物流问题。
• 实际适用性：与现有的量子框架相比，该方法实现了卓越的可扩展性，使其成为现实世界中大规模机队管理的可行候选方案。
• 硬件对齐：通过利用硬件高效的 ansatz，该方法与当前及近期量子设备的能力相一致。

承认的局限性

作者谦逊地指出了若干局限性：

• 理论差距：对于所使用的特定坐标下降实现，没有关于收敛率或收敛保证的形式理论证明。
• VQE 理论：没有理论证明支持 VQE 在此类优化问题上优于经典方法的特定优势；结果是实证的。
• 模型简化：无人机调度模型假设无人机相同且路线已预先计算，简化了现实世界物流系统的复杂性，后者可能涉及异构机队和动态路由。