量子算法结合控制理论，高效求解大规模图优化问题
QuantGraph: A Receding-Horizon Quantum Graph Solver
- 分两阶段：先局部找最优路径，再全局精调
- 搜索空间缩减最高达60%，固定预算下精度提升2倍
- 融合模型预测控制，提升稳定性与计算效率
动态规划是图优化的核心方法，但随问题规模增长而性能下降。本文提出QuantGraph，一种两阶段量子增强框架，将局部与全局图优化问题转化为离散轨迹空间上的量子搜索。第一阶段在不考虑完整路径的前提下，寻找局部最优转移序列，其累积代价作为阈值用于剪枝搜索空间（特定案例中最多减少60%）。第二阶段基于该阈值进行全局优化，两个阶段均采用格罗弗自适应搜索变体。为实现可扩展性与鲁棒性，借鉴控制理论思想，将全局阶段嵌入滚动时域模型预测控制框架中，此经典层稳定并引导量子搜索，提升精度并降低计算负担。实际应用中，闭环系统表现出强鲁棒性与更低的整体复杂度。值得注意的是，在固定查询预算下，QuantGraph实现控制离散化精度翻倍，同时仍享有相比经典方法的二次加速优势。
原文摘要 · Abstract (English)
Dynamic programming is a cornerstone of graph-based optimization. While effective, it scales unfavorably with problem size. In this work, we present QuantGraph, a two-stage quantum-enhanced framework that casts local and global graph-optimization problems as quantum searches over discrete trajectory spaces. The solver is designed to operate efficiently by first finding a sequence of locally optimal transitions in the graph (local stage), without considering full trajectories. The accumulated cost of these transitions acts as a threshold that prunes the search space (up to 60% reduction for certain examples). The subsequent global stage, based on this threshold, refines the solution. Both stages utilize variants of the Grover-adaptive-search algorithm. To achieve scalability and robustness, we draw on principles from control theory and embed QuantGraph's global stage within a receding-horizon model-predictive-control scheme. This classical layer stabilizes and guides the quantum search, improving precision and reducing computational burden. In practice, the resulting closed-loop system exhibits robust behavior and lower overall complexity. Notably, for a fixed query budget, QuantGraph attains a 2x increase in control-discretization precision while still benefiting from Grover-search's inherent quadratic speedup compared to classical methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。