通过约束感知初始化与混合XY–X混合算子提升车辆路径问题中量子近似优化算法的可行性

《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》:Improving feasibility in the quantum approximate optimization algorithm for vehicle routing via constraint-aware initialization and hybrid XY– X mixing

【字体: 大 中 小 】 时间:2026年10月01日 来源:TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 8.4

编辑推荐:

   •约束感知的初始化将概率集中在结构化的VRP状态上。•混合XY-X混合器在保留选定约束的同时允许探索。•所提出的量子线路提高了最优解概率和能隙。•逐块XY-QAOA是一个比标准QAOA更强的基线。•硬件噪声因增加的双量子比特门开销而降低了增益。 引言 在经典交通和智能交通

  

•约束感知的初始化将概率集中在结构化的VRP状态上。•混合XY-X混合器在保留选定约束的同时允许探索。•所提出的量子线路提高了最优解概率和能隙。•逐块XY-QAOA是一个比标准QAOA更强的基线。•硬件噪声因增加的双量子比特门开销而降低了增益。

引言

在经典交通和智能交通系统(ITS)中,高效的路由规划一直并将继续在促进交通网络和供应链的更优决策中发挥关键作用。一个持续受到关注的根本性问题是车辆路径问题(VRP;Toth和Vigo,2002),它是对旅行商问题(TSP;Clarke和Wright,1964,Flood,1956)的扩展,并包含诸如容量受限车辆路径问题(CVRP;Ralphs等,2003)等变体。这些问题寻求能够最小化距离、燃料或时间等成本的路径,在城市物流和出行服务中扮演着重要角色。

VRP变体是NP难问题,精确算法随着问题规模的增大会变得计算上不可行。因此,经典求解器通常依赖启发式方法或近似算法来满足运行时间要求。这促使人们探索用于VRP及相关具有重大实际影响的组合问题的替代计算算法和框架。量子计算激励了关于量子叠加、纠缠和干涉能否通过更有效地搜索巨大的解空间来帮助解决NP难问题的研究。尽管当前的量子设备运行在含噪中等规模量子(NISQ)区间,仅有数十到数百个量子比特且噪声显著,但该领域正快速发展(Preskill,2018),近年来我们见证了门保真度和读出保真度的显著改善(Chen等,2023,Li等,2023,Marxer等,2025,Wang等,2024)。

组合优化的一个突出量子方法是量子近似优化算法(QAOA;Farhi等,2014)。QAOA是一种混合量子-经典算法,通过将目标函数编码在参数化量子线路中并使用经典优化器调谐其参数,来寻求困难组合优化问题的高质量近似解。通过在n个量子比特上交替应用问题特定的代价酉算子和混合酉算子,标准QAOA产生一个参数化量子态。在合适的角度和足够大的深度p下,测量该量子态可以在2?个计算基比特串中获得高质量解。1QAOA已被应用于多种优化问题,包括最大割(MaxCut;Farhi等,2014)、最大独立集(MIS;Choi和Kim,2019,Zhou等,2020)、二元漆店问题(BPSP;Streif等,2021)、二元线性最小二乘(BLLS;Borle等,2021)、多背包问题(Awasthi等,2023)、车辆路径问题(Azfar等,2025,Carmo等,2025),以及更一般地,二次无约束二元优化(QUBO)问题(Moussa等,2022)。2

在QAOA中实现VRP的一个常见步骤是将问题公式化为QUBO,或等价地公式化为伊辛模型(Ising,1925)。3这种公式化通常通过将约束作为惩罚项纳入,从而将约束优化问题转化为无约束问题。理想情况下,编码在不引入额外二元变量(即量子比特)或大幅增加线路复杂性的情况下捕捉所有约束。鉴于近期设备有限的量子比特数,使用尽可能少二元决策变量的公式化尤为有价值。大量文献探讨了VRP的替代QUBO/伊辛编码(Palackal等,2023),以及选择惩罚权重的实用指南(Monta?ez-Barrera等,2024)和参数搜索策略。这些选择直接影响QAOA的资源需求和所产生解的质量。我们的关注点是一个不同但同样重要的问题:如何在QAOA方法中更有效、更稳健地促进解的可行性。因此,我们不对替代公式化或惩罚权重设计进行深入讨论,而将感兴趣的读者引向现有的QUBO编码和惩罚选择文献。

在以伊辛模型框架公式化VRP用于QAOA时,二元决策变量x?∈{0, 1}通过z?=1-2x?(等价地,x?=(1-z?)/2)映射为自旋变量z?∈{-1, +1}。标准QAOA然后从均匀叠加|ψ????=|+???开始,这为{0, 1}?中的每个计算基比特串赋予非零振幅,因此在实例可行时包括所有可行解以及最优解。缺点是,对于VRP编码,可行性通常仅占2?个比特串的极小部分。例如,考虑一个具有两辆车和三个节点(含仓库)的玩具VRP,在基于有向链路的编码下具有六个二元弧变量,使得每个候选解对应一个6量子比特串|x?x?x?x?x?x??。在2?=64个可能串中,只有少数满足路由约束,因此可行比例可以小至1/64。

混合器的选择进一步加剧了这一问题。最常见的选择是横场(Pauli-X)混合器,它施加相同的单量子比特X旋转,从而在所有量子比特上实现独立的比特翻转。由于这种独立翻转通常不尊重问题约束,因此可行性在QAOA演化过程中得不到保持。例如,如果问题结构施加约束x?+x?=1,那么量子比特(5, 6)上的可行配置形成由{|01??,?, |10??,?}张成的子空间。该子空间中的等权态为(|01??,?+|10??,?)/√2。然而,翻转任一个量子比特都可能将可行配置映射为|00??,?或|11??,?,从而破坏可行性。

保约束的替代方案,如XY混合器,通过在选定量子比特对上交换|01??|10?来操作,同时守恒1的总数(汉明权重)。这一守恒定律有助于维持某些类别的约束,但也意味着每个汉明权重扇区独立演化。因此,如果可行VRP解位于某个特定权重扇区k(例如,上述六变量玩具编码中k=4),那么任何不匹配权重的固定权重初始化(如权重一的W态)在XY混合器下无法到达可行扇区。此外,由于XY混合器无法改变任何基态分量的汉明权重,任何最初赋予可行权重扇区之外比特串的振幅永远无法被引导至可行性,即使那些比特串已满足部分约束。在这方面,均匀Pauli-X混合器可能具有优势:通过允许独立比特翻转从而改变汉明权重,它至少保留了从任意比特串移动到可行解的可能性。例如,在相同的六变量设置中,初始叠加中相当一部分可能已经满足某些约束(例如,涉及x?, x?, x?, x?的那些约束),如果剩余的违规需要改变1的总数,那么严格的权重守恒演化将无法利用这种部分可行性。这些观察促使我们强调开发能更稳健地促进解可行性的混合器和初始化策略,而不是对替代伊辛/QUBO编码或惩罚权重设计进行详尽讨论。

在本研究中,我们从两个互补的角度解决可行性瓶颈。首先,不从所有2?个比特串的均匀叠加初始化,而是通过将由问题结构精心选定的状态子集限制为叠加支撑集,构造一个约束感知的初态。这种限制大幅减少了获得非零振幅的基态数量,同时保留了所测实例的所有可行解(已通过穷举验证),从而提高了初始化时的可行与不可行比率。与B?rtschi和Eidenbenz(2020)中QAOA的Grover混合器变体不同,后者的初始化仅支撑在完全可行的状态上,所提出的支撑集通过选定局部约束来指定,不需要显式构造完整的可行集。这一区别涉及逻辑支撑集的构造;在指定叠加态制备的门级代价取决于所选的状态制备分解,且未包含在本文的噪声模型中。其次,我们提出一种具有选定约束保持而非完全可行子空间保持保证的混合XY-X混合器。初始化仅编码选定局部约束,XY交换项保持选定的一热或重叠结构,X混合项在受保护结构之外的量子比特上保留探索能力,而剩余的VRP约束由QUBO惩罚项和后续变分优化处理。在测试的小型VRP实例和模拟环境中,所提出的初始化和混合器改进了可行性导向的性能,尽管相对优势在含噪有限采样模拟中有所减弱。

文献综述

过去几十年来,量子计算作为处理经典方法难以胜任的计算任务的潜在手段,吸引了广泛注意(Preskill,2023,Shor,1994,Steane,1998)。n量子比特系统的希尔伯特空间维度随n指数增长,这一特性通常被称为指数并行性(Rieffel和Polak,2000)。因此,一个n量子比特的寄存器可以被制备在多达2?个计算基态的相干叠加中,从而一

概念综述

量子计算与经典计算存在根本差异。本节介绍理解所提方法所需的概念和定义。

第一个概念是张量积,它将向量空间组合以形成更大的向量空间,是多体系统量子力学的核心(Nielsen和Chuang,2010)。为了具体说明张量积,设A为m×n矩阵,B为p×q矩阵。它们的张量积具有以下矩阵

方法论

本节首先介绍标准的车辆路径公式化和QAOA,然后深入解释所提出的约束感知初始化和混合XY-X混合器。

实验

本节评估所提出的QAOA框架(结合约束感知初始化与混合XY-X混合器)在一个三节点玩具VRP实例和两个四节点VRP基准实例上的表现。三节点实例提供了一个透明的环境来解释所提出的初始化和混合器,而两个四节点实例则检验当量子比特数从六个增加到十二个时观察到的行为是否保持稳定。实验设计有四个主要

结论

本研究探讨如何通过明确解决约束组合优化中固有的可行性问题来提高QAOA对车辆路径问题的有效性。在标准QAOA下,常规的均匀叠加初始化将概率质量分布于整个希尔伯特空间,而标准Pauli-X混合器在不显式尊重问题约束的情况下探索该空间。对于可行解通常仅占极小部分的VRP实例,一个C

作者贡献声明

Yuan-Zheng Lei:写作-初稿,可视化,方法论,调查研究。Yaobang Gong:写作-审阅与编辑,验证。Xianfeng Terry Yang:写作-审阅与编辑,验证,监督,项目管理,方法论,概念化。Nii Attoh-Okine:写作-审阅与编辑,概念化。

Yuan-Zheng Lei | Yaobang Gong | Xianfeng Terry Yang | Nii Attoh-Okine
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号