Optimality-Preserving Decomposition for Scalable QAOA in Natural-Language-Guided Multi-Drone Assignment

📄 arXiv: 2606.14252v1 📥 PDF

作者: Junyeop Bang, Byongho Lee, Dohyun An, Hwangnam Kim

分类: cs.RO

发布日期: 2026-06-12

备注: 10 pages, 2 figures, 3 tables, preprint

💡 一句话要点

提出一种优化保持分解方法以解决多无人机任务分配问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 量子优化 多无人机调度 自然语言处理 QUBO约束 动态规划 机器学习 量子计算

📋 核心要点

  1. 随着无人机数量的增加，区域分配问题变得复杂且难以解决，现有经典方法难以应对NP难题的挑战。
  2. 本文提出了一种结合大型语言模型和量子优化的框架，通过自然语言指令生成QUBO约束，优化多无人机任务分配。
  3. 实验结果显示，该方法在理想情况下实现100%全局最优解，在真实采样中达到96.3%的成功率，显著提升了任务分配的效率。

📝 摘要（中文）

随着多无人机机队规模的扩大，区域分配迅速演变为一个难以处理的NP难题，超出了经典穷举搜索的能力。尽管量子优化有望打破这些经典瓶颈，但将复杂的空间任务从人类意图映射到受限的量子硬件仍然是一个严峻的挑战。为了解决这一问题，本文提出了一个端到端框架，将经过微调的大型语言模型（LLM）前端与高度可扩展的领域特定量子-经典后端相结合。前端利用监督微调（SFT）和直接偏好优化（DPO）将自由形式的自然语言指令转换为结构稳健的二次无约束二进制优化（QUBO）约束。为了克服近端量子设备的严格量子比特限制，框架引入了一种新颖的约束保持图划分器和基于压缩分隔符的动态规划合并。实验证明，该架构在理想化的oracle案例中恢复全局最优解的成功率达到100%，在真实QAOA采样下为96.3%，使得自然语言引导的任务分配在以前难以处理的规模上成为可能。

🔬 方法详解

问题定义：本文旨在解决多无人机区域分配问题，该问题随着无人机数量的增加而变得复杂，现有的经典方法在处理NP难题时面临性能瓶颈。

核心思路：提出的框架通过结合大型语言模型和量子优化技术，能够将自然语言指令有效转化为量子计算所需的QUBO约束，从而优化任务分配。

技术框架：整体架构包括前端的自然语言处理模块，利用SFT和DPO生成QUBO约束，后端则是量子优化模块，采用约束保持图划分和动态规划合并技术，确保在量子比特限制下的高效计算。

关键创新：最重要的创新在于引入了约束保持图划分器和压缩分隔符的动态规划合并方法，这使得在量子设备的限制下仍能有效处理复杂的任务分配问题。

关键设计：在设计中，采用了W态初始化和XY混合器来结构性地编码约束，同时在CVaR-QAOA中实现了高效的量子优化，确保了模型的紧凑性和高效性。

📊 实验亮点

实验结果表明，所提出的框架在理想化的oracle案例中成功恢复全局最优解的比例达到100%，在真实QAOA采样下的成功率为96.3%，显著超越了传统方法的性能限制。

🎯 应用场景

该研究的潜在应用领域包括无人机调度、物流配送和智能交通系统等。通过实现自然语言引导的任务分配，能够大幅提升多无人机系统的操作效率，具有重要的实际价值和未来影响。

📄 摘要（原文）

As multi-drone fleets scale, zone assignment rapidly evolves into an intractable NP-hard combinatorial problem that overwhelms classical exhaustive search. While quantum optimization promises to shatter these classical bottlenecks, mapping complex spatial tasks from human intent to restricted quantum hardware remains a severe challenge. To bridge this gap, we present an end-to-end framework integrating a fine-tuned Large Language Model (LLM) front-end with a highly scalable, domain-specific quantum-classical backend. The front-end utilizes Supervised Fine-Tuning (SFT) and Direct Preference Optimization (DPO) to translate free-form natural language instructions into structurally robust Quadratic Unconstrained Binary Optimization (QUBO) constraints without false negatives. To overcome the strict qubit limits of near-term quantum devices, our framework features a novel constraint-preserving graph partitioner and a compressed separator-based dynamic programming (DP) merge. By structurally encoding constraints via W-state initialization and XY-mixers in Conditional Value-at-Risk Quantum Approximate Optimization (CVaR-QAOA), the pipeline stays highly compact. Empirical results demonstrate that this architecture circumvents classical scaling walls, recovering the global optimum on 100% of idealized oracle cases and 96.3% under real QAOA sampling, enabling natural-language-guided task allocation at previously intractable scales.