改进量子优化算法,用梯度信息加速求解全局最优。
Quantum Optimization via Gradient-Based Hamiltonian Descent
- 结合梯度信息改进量子哈密顿下降法,提升优化效率。
- 在复杂问题上收敛速度比现有方法快一个数量级。
- 适合需要高效搜索全局解的高维非凸优化场景。
随着机器学习的快速发展,一阶算法因其计算高效和低内存需求成为现代优化技术的核心。近期,加速梯度方法与阻尼重球运动之间的联系,特别是在哈密顿动力学框架下,启发了连续优化中新型量子算法的发展。其中,量子哈密顿下降(QHD)利用量子隧穿效应逃离鞍点和局部极小值,有助于在复杂优化景观中发现全局解。然而,QHD存在收敛速度慢于经典梯度方法、在高度非凸问题中鲁棒性差等问题,且原始形式主要依赖函数值信息,限制了其效果。受高分辨率微分方程对经典方法加速机制的启示,本文提出在QHD中引入梯度信息,形成梯度增强型量子哈密顿下降(gradient-based QHD)。该方法显著加快收敛速度,并大幅提升找到全局解的概率。数值模拟显示,在具有挑战性的实例中,该方法性能优于现有量子与经典方法至少一个数量级。
原文摘要 · Abstract (English)
With rapid advancements in machine learning, first-order algorithms have emerged as the backbone of modern optimization techniques, owing to their computational efficiency and low memory requirements. Recently, the connection between accelerated gradient methods and damped heavy-ball motion, particularly within the framework of Hamiltonian dynamics, has inspired the development of innovative quantum algorithms for continuous optimization. One such algorithm, Quantum Hamiltonian Descent (QHD), leverages quantum tunneling to escape saddle points and local minima, facilitating the discovery of global solutions in complex optimization landscapes. However, QHD faces several challenges, including slower convergence rates compared to classical gradient methods and limited robustness in highly non-convex problems due to the non-local nature of quantum states. Furthermore, the original QHD formulation primarily relies on function value information, which limits its effectiveness. Inspired by insights from high-resolution differential equations that have elucidated the acceleration mechanisms in classical methods, we propose an enhancement to QHD by incorporating gradient information, leading to what we call gradient-based QHD. Gradient-based QHD achieves faster convergence and significantly increases the likelihood of identifying global solutions. Numerical simulations on challenging problem instances demonstrate that gradient-based QHD outperforms existing quantum and classical methods by at least an order of magnitude.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。