一种基于量子机器学习的优化求解方法

摘要: 本发明涉及量子计算,特别涉及一种基于量子机器学习的优化求解方法。背景技术:1、随着量子计算、人工智能、高性能计算和科学计算技术的发展,变分量子算法逐渐应用于物理...
一种基于量子机器学习的优化求解方法

本发明涉及量子计算,特别涉及一种基于量子机器学习的优化求解方法。

背景技术:

1、随着量子计算、人工智能、高性能计算和科学计算技术的发展,变分量子算法逐渐应用于物理系统求解和优化问题求解。根据待求解对象及目标来源的不同,现有基于机器学习的量子优化算法主要包括物理系统基态求解和优化问题求解两打类:

2、一方面,在生物化学分子、凝聚态材料以及量子多体系统的研究中,通常需要求解物理系统的基态能量、近似基态及相关物理可观测量。由于物理系统的希尔伯特空间维度随粒子数量或量子模式数量增加而快速增长,直接对目标哈密顿量进行精确对角化通常需要较大的存储资源和计算资源。vqe(variational quantum eigensolver,变分量子本征求解器)等变分量子算法通过构建参数化量子态,测量物理系统的目标哈密顿量在所述参数化量子态下的能量期望值,并根据所述能量期望值迭代调整参数,以获得基态能量估计值、近似基态表示或相关物理可观测量。

3、另一方面,在物流调度、资源分配、图优化、路径规划、约束满足、布尔可满足性、组合设计、连续参数决策以及离散—连续混合决策等优化任务中,需要从候选变量空间中确定满足目标函数和约束条件的优化结果。对于离散优化或组合优化任务,可以将离散决策变量编码为量子比特或其他计算模式,并将目标函数和约束条件编码为代价哈密顿量,通常采用qaoa(quantum approximate optimization algorithm,量子近似优化算法)或其他变分量子优化算法调整参数化量子模型,使其测量概率趋向于低代价变量取值。

4、然而,现有基于量子机器学习的优化方法仍存在以下不足:

5、第一,现有结构化拟设具有较高的线路深度和实现复杂度。例如,在分子体系近似基态求解中,酉耦合簇单双激发拟设(unitary coupled cluster singles and doubles,uccsd)通常包含数量随自旋轨道数和电子数增加而快速增长的单激发项和双激发项,将所述激发项映射为量子比特算符并通过量子门序列实现时,通常还需要进行算符分解、费米子—量子比特映射和乘积公式近似,可能产生较多的单量子比特门和双量子比特门,导致参数数量、量子线路深度和执行时间增加。在现阶段含噪量子计算设备上,较深的量子线路容易累积门误差、退相干误差和测量误差,并可能增加损失函数及其梯度的测量与训练开销,限制可处理物理系统的规模和求解精度。

6、第二,现有通用变分拟设容易出现由模型结构导致的贫瘠高原。所谓贫瘠高原,是指在参数化量子模型训练过程中,损失函数关于可训练参数的梯度幅值随系统规模或线路深度快速衰减,使优化器难以获得有效下降方向。其一类主要成因来自量子神经网络或参数化量子线路本身。当硬件高效型量子神经网络采用大量随机单比特旋转门和纠缠门堆叠时,随着量子比特数和线路深度增加,线路整体容易趋近随机酉演化或酉设计,导致局部可观测量或全局损失函数的梯度方差快速衰减。此类贫瘠高原主要由线路随机化程度过高以及参数化结构缺少约束所引起。量子近似优化算法在加深层数以提高表达能力时,也会增加参数优化难度,其训练稳定性同样受到线路深度、噪声和梯度估计误差的影响。

7、第三,损失函数和梯度估计开销较高。现有量子机器学习组合优化方法通常需要反复执行参数化量子线路,并通过测量估计损失函数或梯度。对于包含大量参数的量子线路,梯度通常依赖参数平移法、有限差分法、随机梯度估计法或同时扰动随机近似法获得。每次参数更新往往需要多次线路执行和大量测量采样。当组合优化目标函数包含大量局部代价项、约束惩罚项或奖励项时,损失函数需要对多个哈密顿量项或多个采样结果进行估计,测量开销和统计误差随问题规模增大而显著增加。对于量子近似优化算法和变分量子本征求解方法而言,若目标哈密顿量由大量局部项组成,则每轮训练都可能需要大量测量次数来获得稳定的期望值估计。对于真实量子硬件,测量噪声、门误差和退相干进一步增加了损失函数和梯度估计的不确定性,限制了现有方法在大规模组合优化任务中的实用性。

8、第四,大规模经典验证能力不足。现阶段通用量子计算机仍受到量子比特数量、门保真度、退相干时间、连通性和测量噪声等因素限制,在真实量子硬件上开展大规模量子机器学习组合优化实验仍然较为困难。因此,大规模经典模拟验证对于算法设计、参数调试和性能评估具有重要意义。但是,现有经典模拟方法多依赖通用态矢量模拟、密度矩阵模拟、mps(matrix product state,矩阵乘积态)或一般张量网络收缩方法。通用态矢量模拟的存储开销随量子比特数呈指数增长,密度矩阵模拟的开销更高;一般张量网络方法虽然可以利用部分低纠缠结构,但对于高连接度、深层线路或复杂测量结构,其收缩成本仍可能快速增长。实际应用中,通用经典模拟通常只能支持约三十个变量或量子比特量级的量子机器学习组合优化验证,难以满足百变量乃至更大规模组合优化问题的算法开发需求。矩阵乘积态等一维张量网络方法适合低纠缠或一维局部结构问题,但对于具有复杂约束图、高阶局部代价项、长程耦合或较高有效纠缠的组合优化任务,所需键维可能迅速增大,一般张量网络的收缩顺序和收缩成本也会随问题结构复杂度显著增加。因此,现有经典模拟工具难以同时满足大规模变量、可训练性分析、损失函数计算和候选解采样的需求。

9、综上,现有qaoa、vqe、硬件高效量子神经网络以及mps/张量网络等方法分别存在层数与表达能力权衡、哈密顿量测量开销、参数化线路导致的贫瘠高原、组合优化目标本身导致的梯度稀疏或训练困难、问题结构适配不足以及张量网络收缩成本增长等问题。现有技术仍缺少一种能够同时兼顾组合优化任务结构、量子机器学习可训练性、损失函数和梯度可计算性以及大规模经典验证能力的基于量子机器学习的优化求解方法。

技术实现思路

1、鉴于现有量子机器学习的组合优化方法存在参数化结构消耗资源较多、训练过程中易出现贫瘠高原或梯度信号稀疏、损失函数与梯度估计开销较高、真实量子硬件受限于噪声和规模,以及经典通用模拟难以支持大规模验证等问题,本发明提出一种基于量子机器学习优化求解方法,采用如下技术方案:

2、费米子高斯拟设,由费米子二次型、majorana二次型、自由费米子高斯演化或与其对应的费米子高斯可计算结构生成、保持或表征。该结构能够通过二阶费米子关联矩阵、bogoliubov-de gennes关联矩阵、majorana协方差矩阵、正交变换矩阵、pfaffian、grassmann高斯积分、平面匹配门张量网络、平面图完美匹配或其组合进行经典计算。由此,本发明能够避免通用态矢量模拟所需的指数级存储开销,并提高损失函数、梯度和采样过程的可计算性。

3、对于由无结构随机参数化量子线路导致的贫瘠高原,本发明通过费米子高斯结构限制可训练态空间或可计算结构,使模型不在完整指数维希尔伯特空间中进行无结构随机搜索,从而降低由随机酉演化或酉设计导致的梯度集中风险。本发明实施方式概述如下:

4、s1、任务编码

5、根据待求解的优化任务获取目标哈密顿量。例如,当所述待求解对象为优化任务时,获取所述优化任务中的原始决策对象、目标函数和约束条件,将所述原始决策对象编码为布尔变量,将所述优化任务中的各类约束和目标项转化为目标哈密顿量。

6、例如,当所述待求解对象为分子体系、凝聚态材料或其他量子多体物理系统的近似基态求解任务时,获取所述物理系统的结构信息、物理自由度、相互作用关系,构建所述物理系统的哈密顿量;根据计算规模或计算精度要求,对所述电子结构哈密顿量或物理哈密顿量进行基空间选择、自由度截断、有效模型转换和算符映射等处理,即可将其转换为由量子比特对应的目标哈密顿量。

7、s2、构造参数化费米子高斯结构并进行参数优化

8、本发明采用参数化费米子高斯结构作为基本拟设。该方案通常不依赖于优化目标的选取:执行演化的哈密顿量在费米子编码或majorana编码下,具有高斯结构(即二次结构),而目标哈密顿量则具有更一般结构。如此既能保证变分量子态的训练效果,又能最大程度上适配一般问题。有时为进一步提高训练效率,也可根据优化问题结构和目标哈密顿量结构,采用特定类型的费米子高斯变分量子态。

9、本发明包括两条执行方式:经典计算机模拟执行方式和量子硬件执行方式,两种方式可混合执行。

10、s2.1、经典计算机模拟执行方式

11、在经典计算机模拟执行方式中,在经典计算设备上构造由可训练参数控制的费米子高斯可计算结构。所述经典计算设备可以包括中央处理器、图形处理器、张量处理器、现场可编程门阵列、专用集成电路、计算集群、云计算平台或其组合。

12、在一种实施方式中,所述费米子高斯可计算结构包括态表示、演化表示和计算表示中的至少一种。

13、其中,所述态表示可以包括费米子关联矩阵、bogoliubov-de gennes关联矩阵、majorana协方差矩阵、费米子高斯态规范形式或其组合。

14、所述演化表示用于表征保持费米子高斯结构的参数化演化。所述演化表示可以包括费米子模式线性变换矩阵、bogoliubov变换矩阵、majorana正交变换矩阵、二次费米子哈密顿量系数矩阵、二次majorana哈密顿量系数矩阵、匹配门线路参数结构或其组合。

15、所述计算表示用于计算局部代价项期望值、计算基测量概率、边缘概率、条件概率、损失函数、损失函数梯度、采样概率或布尔变量比特串样本。所述计算表示可以包括wick展开、pfaffian、行列式、grassmann高斯积分、kasteleyn矩阵、平面匹配门张量网络、带权平面图、平面图完美匹配或其组合。

16、在一种具体实现中,所述经典计算机模拟执行方式采用majorana协方差矩阵表示费米子高斯结构参数化量子态。对于个费米子模式,定义个majorana算符,费米子高斯态可由一个的实反对称协方差矩阵表示:

17、

18、其中,为majorana算符。保持费米子高斯结构的参数化演化可以在协方差矩阵层面表示为:

19、

20、其中,为由可训练参数控制的majorana正交变换矩阵。

21、由此,经典计算设备无需显式存储维量子态矢量,而仅需维护多项式规模的费米子高斯可计算结构。与传统态矢量模拟需要存储个复振幅、存储复杂度为相比,采用majorana协方差矩阵时仅需维护矩阵,存储复杂度为。例如,对于个变量,传统态矢量模拟需要维护个复振幅,而本发明仅需维护一个的协方差矩阵,即约个矩阵元素;若利用其实反对称结构,还可以进一步减少独立存储元素数量。

22、s2.2、量子硬件执行方式

23、在量子硬件执行方式中,在量子计算设备上执行由可训练参数控制且保持费米子高斯结构的参数化量子演化,以制备费米子高斯结构参数化量子态。

24、所述保持费米子高斯结构的参数化量子演化可以在选定的费米子模式表示、量子比特编码表示或物理模式表示下实现费米子二次型演化、majorana二次型演化、自由费米子高斯演化或保持费米子高斯结构的参数化量子过程。所述量子计算设备不限于门模型量子线路设备,也可以包括模拟量子演化设备、数字-模拟混合量子设备、专用自由费米子量子模拟平台或其他能够实现费米子高斯结构演化的物理设备。

25、在一种实施方式中,所述参数化量子演化由费米子二次型哈密顿量生成:

26、

27、其中,和分别表示费米子产生算符和湮灭算符,表示粒子数守恒的模式混合系数,表示粒子数非守恒的配对系数。由于所述哈密顿量为费米子二次型,其生成的演化保持费米子高斯结构。

28、在另一种实施方式中,所述参数化量子演化由majorana二次型哈密顿量生成:

29、

30、其中,为实反对称矩阵,为majorana算符。该演化在majorana模式空间中对应正交变换,因此能够保持费米子高斯结构。

31、在门模型量子线路实现中,所述参数化量子演化可以通过匹配门量子线路、自由费米子高斯演化线路、费米子线性光学线路、givens旋转网络、bogoliubov变换网络、fermionic swap辅助的费米子高斯线路或其组合实现。在模拟量子演化实现中,可以通过可调哈密顿量直接实现费米子二次型演化、majorana二次型演化或自由费米子高斯演化。在数字-模拟混合实现中,可以通过离散量子门序列与连续哈密顿量演化的组合实现保持费米子高斯结构的参数化量子演化。在专用自由费米子量子模拟实现中,可以通过自由费米子模式、费米子线性光学模式、可调自旋链、冷原子或光晶格自由费米子系统、量子点阵列、majorana模式平台或其组合实现。

32、在具体实施方式中,优化问题在量子设备上所需的参数化量子态,可由费米子高斯演化作用在计算基的全0态或0/1初始态,或基的张量积上得到。

33、s3、损失函数构建

34、在经典计算机模拟执行方式中,所述损失函数可以基于局部代价项期望值、局部比特串统计、目标函数期望值或经典采样平均代价构建。在量子硬件执行方式中,所述损失函数可以基于组合优化目标哈密顿量的测量期望、局部对角哈密顿量项的测量结果或计算基测量样本的平均代价构建。

35、所述损失函数可以包括目标函数值、代价值、能量值、约束违反程度、约束满足程度、奖励值、惩罚值或其组合。

36、s3.1、经典计算机模拟执行方式

37、在经典计算机模拟执行方式中,对于每个局部代价项,基于所述费米子高斯可计算结构在该局部代价项所涉及变量子集上的局部计算表示,确定对应变量子集的局部比特串统计,并根据所述局部比特串统计计算或估计该局部代价项的期望值。进一步地,根据多个局部代价项的期望值确定损失函数,并基于所述损失函数或其梯度更新所述费米子高斯可计算结构的可训练参数。

38、s3.2、量子硬件执行方式

39、在该量子硬件执行方式中,基于所述费米子高斯结构参数化量子态对组合优化目标哈密顿量的测量结果,计算或估计损失函数;或者,对所述费米子高斯结构参数化量子态进行计算基测量,得到布尔变量比特串样本,并基于样本评价值估计损失函数。

40、在参数优化完成后,更新后的费米子高斯结构参数化量子态可以作为优化候选解,也可进行计算基测量,得到一个或多个布尔变量比特串,并将所述布尔变量比特串解码为优化候选解。

41、由此,本发明既可以在经典计算设备上利用费米子高斯结构的可模拟性进行多项式资源模拟和训练,也可以在量子计算设备上直接执行保持费米子高斯结构的参数化量子演化。两种执行方式均可用于组合优化目标函数的损失评估、参数更新和候选解生成,并且可以根据硬件条件、问题规模和计算资源选择单独使用或组合使用。

42、s4、参数优化

43、基于所述损失函数或所述损失函数的梯度,更新可训练参数。

44、在经典计算机模拟执行方式中,所述梯度可以通过费米子高斯经典模拟方法、自动微分、解析微分、有限差分、随机梯度估计或其组合获得。

45、在量子硬件执行方式中,所述梯度可以通过量子测量、参数平移法、有限差分法、随机梯度估计法、无梯度优化方法、混合量子经典优化方法或其组合获得。

46、s5、得到候选解

47、根据预设的终止条件,在优化结束后,根据返回损失函数值或变分量子态,得到优化问题候选解。对于生物化学分子及物理系统,更新后的费米子高斯态可进一步用于模拟演化;对于组合优化问题,可基于更新后的费米子高斯可计算结构进行经典采样,并将所述布尔变量比特串解码为组合优化候选解。

48、与现有技术相比,本发明至少具有以下有益效果:

49、一、广泛适用于各类优化问题

50、本发明适用于多种生物化学、物理系统基态求解问题,也适用于各类组合优化问题,适配一般的变分量子算法框架。

51、二、通过结构化费米子高斯拟设缓解量子线路中的训练困难

52、现有硬件高效拟设通常通过随机单比特旋转门和纠缠门的堆叠提升表达能力,但随着量子比特数量和线路深度增加,参数化线路容易趋向近似随机酉演化,导致损失函数梯度衰减,从而出现贫瘠高原型训练困难。

53、本发明采用费米子高斯可模拟参数化拟设,使参数化量子态限制在具有明确代数结构的费米子高斯态族中。该结构化拟设避免了在完整希尔伯特空间中进行无约束随机搜索,使优化过程不再依赖无结构深层随机量子线路,有助于减轻由随机酉演化引起的梯度衰减现象,从而提高训练过程的稳定性,并降低出现贫瘠高原型优化停滞的风险。

54、进一步地,费米子高斯拟设可以由匹配门线路、givens旋转网络、bogoliubov变换网络、自由费米子演化、非相互作用费米子演化、二次费米子哈密顿量演化或者二次majorana哈密顿量演化实现。该类拟设具有清晰的代数结构和物理含义,相较于无结构随机量子线路,更便于进行参数初始化、梯度计算、结构分析和硬件迁移。

55、三、适合较大规模优化任务的训练和验证

56、本发明采用费米子高斯可模拟参数化拟设生成参数化量子态。该类参数化拟设在量子态演化过程中保持费米子高斯结构,因此在经典计算机模拟时不需要显式存储和更新完整的维量子态矢量。

57、在一种实现方式中,可以使用majorana协方差矩阵、费米子高斯态关联矩阵、正交变换矩阵或者等价的低维数据结构表示和更新参数化量子态。由于这些数据结构的规模随量子比特数量多项式增长,其存储代价通常为,而不是随量子比特数量指数增长,因此本发明能够显著降低经典模拟所需的存储资源和计算资源,使较大规模布尔变量组合优化任务的量子机器学习训练和验证成为可能。

58、对于能够由局部代价项集合表示的组合优化目标,本发明可以将目标哈密顿量分解为多个计算基对角项或者pauli字符串项。由于费米子高斯态的多体关联函数可以由二阶关联矩阵确定,因此这些哈密顿量项的期望值能够通过协方差矩阵、wick定理、pfaffian或者等价方法在经典计算机上计算。

59、因此,在该类任务中,本发明不必依赖真实量子硬件的大量重复测量来估计损失函数,能够减少采样误差和硬件噪声对训练目标的干扰,提高损失函数计算的稳定性和可重复性;同时,本发明还可以利用自动微分、解析微分或者参数移位类方法计算损失函数关于线路参数的梯度,从而降低梯度计算开销。其中,表1为本方法在部分3-sat随机实例应用的经典模拟计算开销(l40 gpu)表,具体表1如下。

60、表1

61、

62、四、能够利用参数化量子态的叠加表示能力提高候选解搜索范围

63、本发明所采用的费米子高斯可模拟参数化量子态包含所有0/1比特串,在-在训练初始阶段可选取随机参数,能够同时表示多个候选解分量,在同一参数化模型内对多个候选解区域进行并行覆盖和筛选,降低单一路径搜索陷入较差局部极小值的风险,并提高获得优质候选解或者满足解的可能性。参数优化过程通过损失函数作用于整个概率分布,使概率质量逐步向低代价、高约束满足率或者满足全部约束的布尔变量比特串及其叠加方向集中,优化得到的量子态往往包含大量高质量近似解。

64、进一步地,对组合优化问题,可以针对所述高质量候选解采用walksat、模拟退火、禁忌搜索或者其他局部搜索的后处理方法,对未满足子句或未满足约束所涉及的变量进行翻转、重采样或者局部修正。由于本发明输出的候选解已经具有较低能量或者较高约束满足率,后处理算法只需在候选解附近进行局部搜索,从而能够减少从随机初始赋值出发搜索的困难,提高获得全局满足解或者更优目标函数值的概率。

65、以3-sat问题为例,3-sat是np完全问题的典型代表。通常,当子句数量约为变量数量的4.267倍时,随机3-sat实例接近有解和无解的相变困难区域,满足解较为稀少,求解难度显著增加。

66、在本发明的经典模拟实验验证中,可以采用带预设满足赋值的随机可满足3-sat实例生成方式。该方式首先随机生成一个预设满足赋值,然后随机生成与该预设满足赋值一致的3-sat子句,从而保证所得公式至少存在一个满足解;同时,子句数量按照约的临界比例设置,以构造接近随机3-sat相变区域的可满足测试实例。

67、在所测试的随机可满足3-sat实例中,本发明的费米子高斯参数化模型能够获得满足方程比例较高的候选解。在20次尝试之内,有显著概率获得方程组的解。其中,表2为本方法与经典方法求解效果对比表,具体表2如下。

68、表2

69、

70、进一步地,针对上述候选解采用walksat局部搜索后处理,对未满足子句涉及的变量进行随机翻转和局部修正,可以进一步搜索得到全局满足解。实验结果表明,在测试条件下,本发明结合walksat后处理能够显著提高求解大规模3-sat实例的成功率。

71、在随机实例测试中,本发明均能够获得满足99%以上子句的高质量候选解。进一步地,针对上述高质量候选解,采用walksat局部搜索技巧,对未满足子句所涉及变量进行随机翻转尝试,即可进一步搜索得到全局满足解。在50组方程的求解实验中,本发明结合walksat后均成功找到全局最优解,实验成功率达到100%。其中,表3为本方法的规模实验性能(50组方程)表,具体表3如下。

72、表3

73、

74、本发明的量子机器学习部分提供了采样高质量候选解,walksat等各类局部搜索方法均可作为可选后处理步骤,用于进一步修正未满足约束并提高获得全局满足解的可能性。二者结合后,能够形成“概率分布学习—候选解采样—局部搜索修正”的组合优化求解流程。

75、五、能够充分利用经典计算和量子硬件资源

76、本发明采用的费米子高斯结构参数化模型具有明确的物理实现基础。其典型实现包括参数化匹配门量子线路、自由费米子高斯演化、非相互作用费米子演化、费米子线性光学演化、givens旋转网络、bogoliubov变换网络以及由二次费米子哈密顿量或者二次majorana哈密顿量生成的参数化量子演化。该类结构不同于通用深层随机量子线路,具有清晰的自由费米子或费米子高斯物理含义,因此既可以在经典计算设备上利用费米子高斯可模拟结构进行训练和验证,也可以在具备相应物理实现能力的量子硬件上执行参数化拟设演化和测量采样。

77、由此,本发明并非仅限于纯量子算法或纯经典算法,而是能够形成一种经典—量子融合的优化求解框架。在该框架中,经典计算设备主要用于问题建模、目标哈密顿量构造、损失函数定义、参数更新以及采样结果后处理;量子硬件则用于执行保持费米子高斯结构的参数化量子拟设演化,并通过计算基测量产生布尔变量比特串样本。测量得到的比特串样本再返回经典计算设备,由经典计算设备计算其目标函数值、约束满足率或者约束违反程度,并进行候选解筛选、参数反馈更新以及局部搜索后处理。

78、相比于纯经典模拟算法,引入量子硬件执行费米子高斯拟设计算,可以减少在经典计算设备上显式进行大规模矩阵更新、关联矩阵传播或概率分布采样的计算负担;尤其是在能够以物理演化方式直接实现费米子高斯结构的参数化变换的情况下;并且在最终通过采样快速产生大量布尔比特串样本,省去经典计算的模拟采样代价;还可获得更大量子态空间表达能力,从而具有更大的优化潜能。

79、本发明既保留了费米子高斯结构在经典侧可训练、可验证、可预训练的优点,又能够在具备相应硬件条件时将拟设演化和采样任务交由量子硬件执行,从而降低经典模拟负担,利用量子硬件的物理演化和测量采样能力,并为未来更大规模优化任务的量子—经典混合求解提供实现路径。