一种基于量子演化的搜索方法及系统与流程
本发明涉及量子计算及量子控制技术,具体涉及一种基于量子演化的搜索方法及系统。
背景技术:
1、量子搜索将候选对象编码为量子态,将满足搜索条件的目标对象所对应的量子态称为目标态。通过量子演化,使制备的初始态演化为包含初始态与目标态的叠加态,并提高测量得到目标对象的概率。一类搜索方案采用0/1势能,将目标态与非目标态分别赋予两个势能值。实际搜索问题所对应的势能函数往往具有多个能级,或者可由量子处理器的物理相互作用直接提供一般势能演化。
2、将一般势能转换为0/1势能,会随实现方式引入不同的额外代价。在门模型实现中,可能需要构造查询电路(oracle),以实现相干目标判定、能量比较或势能重编码,并反算相关辅助信息,增加量子门、辅助量子比特和电路深度;在模拟实现中,可能需要额外设计相互作用或调节控制场,以将原有的多能级势能改造成仅具有两个取值的势能。对于判定逻辑复杂或能级调控要求较高的问题,上述转换的实现代价可能较大。因此,在能够实现一般势能演化的条件下,直接利用该势能景观进行搜索,可以减少对上述转换过程的依赖。
3、标准grover搜索通过二值势能产生的演化配合扩散操作实现振幅放大,其中目标态与非目标态分别对应不同的势能值。将该二值势能直接替换为一般多值势能后,通常不再保持标准振幅放大所依据的二维演化结构,这种直接替换并不能保证实现搜索加速。grover类可调相位混合器虽已有与多值目标函数配合的方案,例如grover-mixer qaoa,但采用grover类混合器本身并不保证从给定初始态出发,在一般势能景观中高效找到其他目标态,(参见:lov k. grover,a fast quantum mechanical algorithm for databasesearch,1996,arxiv:quant-ph/9605043;andreas bärtschi、stephan eidenbenz,grovermixers for qaoa: shifting complexity from mixer design to state preparation,2020,arxiv:2006.00354)。
4、绝热量子计算和标准量子近似优化算法常采用局部相互作用,典型形式为单比特翻转项之和,其中作用于第个量子比特。该哈密顿量在计算基底下仅直接耦合相差一个比特的编码态。两个编码态若相差个比特,即汉明距离为,至少需要次单比特翻转才能连接。当这两个态等能、连接路径上的中间态均偏离该能量,且局部混合与问题势能共同作用、处于弱混合的微扰适用区域时,两态之间的有效耦合最早出现在第阶,通过中间态的虚跃迁形成高阶有效转移,(参见:edward farhi、jeffrey goldstone、sam gutmann、michael sipser,quantum computation by adiabatic evolution,2000,arxiv:quant-ph/0001106)。
5、这种高阶有效转移会受到势垒抑制。以单比特翻转强度为、中间态与两端态的能量差量级为为例,一条最短路径对有效耦合的贡献量级为;相差三个比特时,相应单路径贡献为量级。在远小于的条件下,每增加一次所需翻转,就多引入一个小量因子,从而抑制该路径的转移贡献。总有效耦合还取决于路径数量、各中间态能量差及路径贡献的叠加。因此,高阶转移抑制可能限制相距较远的等能态之间的搜索效率;该分析针对上述弱混合及非共振中间态条件。
6、量子近似优化算法通过问题演化与混合操作交替执行并选择演化参数来改善目标函数值,其表现取决于问题实例、混合结构、电路层数及参数选择。目标函数值的改善并不等价于相对于经典搜索的计算加速;采用该交替结构本身,也不保证在计入参数选择、量子演化、测量及重复尝试的代价后获得搜索加速,(参见:edward farhi、jeffreygoldstone、sam gutmann,a quantum approximate optimization algorithm,2014,arxiv:1411.4028)。
7、随机量子电路可由已有单比特操作和多比特相互作用组合构造,具有与可编程量子硬件相适配的实现基础。然而,在变分量子本征求解器(vqe)等依赖参数优化的方法中,在相关电路及目标函数条件下,随机初始化且混合充分的参数化电路可能出现贫瘠高原(barren plateau),使梯度估计和参数训练的代价显著增加。mcclean等人在2018年对此进行了研究。因此,此类变分算法的电路设计通常需要避免出现梯度方差随量子比特数增加而指数衰减所导致的贫瘠高原现象,(参见:jarrod r. mcclean、sergio boixo、vadim n.smelyanskiy、ryan babbush、hartmut neven,barren plateaus in quantum neuralnetwork training landscapes,nature communications,2018,9,4812,doi:10.1038/s41467-018-07090-4)。
8、随机量子电路也已有多比特实验实现。arute等人在2019年报告了采用53个超导量子比特进行随机量子电路采样的实验,以展示特定采样任务中的量子计算优势。该实验表明,随机量子电路已能够在实际硬件上执行,并可用于展示特定任务上的计算加速。然而,计算得更快并不等于解决了有用的问题。该采样实验没有直接解决具有实际需求的搜索问题,其加速演示本身也没有给出解决这类问题的方法。找到能够解决实际问题的有用量子优势,是量子计算领域的核心问题之一,(参见:frank arute等,quantum supremacyusing a programmable superconducting processor,nature,2019,574,505–510,doi:10.1038/s41586-019-1666-5)。
9、对于随机量子电路,关键问题是如何将已经能够实现的混合能力用于有实际目标的计算任务。本发明针对一般势能景观中的搜索,利用随机量子电路所表征的全局混合演化,从制备的初始态寻找满足给定条件的目标态。
10、因此,对于一般势能景观中从已制备初始态寻找其他目标态的任务,仍需使全局混合演化与问题哈密顿量产生的演化配合,实现目标子空间内量子态的相干叠加,以实现搜索加速。
技术实现思路
1、本发明要解决的技术问题是:如何在一般势能景观中,从制备的初始态出发,采用量子演化加速搜索满足给定条件的其他目标态。
2、本发明提供一种基于量子演化的搜索方法,包括以下步骤:获取搜索条件和表征候选对象的问题信息,选定初始态,将问题信息编码为问题哈密顿量,使初始态与目标态集合张成该问题哈密顿量的一个特征子空间,作为目标子空间。
3、配置全局混合演化,用于实现目标子空间内量子态的相干叠加。在量子设备上制备初始态,将问题哈密顿量产生的演化与全局混合演化交替执行或共同实施,使量子系统从初始态向目标态演化。测量演化后的量子系统,并根据测量结果及搜索条件确定搜索结果。
4、初始态根据问题信息选定并通过态制备获得。目标态集合包括与满足搜索条件的对象对应的一个或多个量子态,可以通过搜索条件表述,无需预先列出目标对象。目标子空间由初始态与目标态集合共同张成;它们属于问题哈密顿量的同一特征子空间,具有相同的能量本征值。该子空间以外的能级由问题信息及其编码方式确定。
5、问题哈密顿量演化及初始态与全局混合演化分别配置,再组合形成搜索演化。全局混合演化可采用多比特随机量子电路所表征的量子演化,或者由hadamard矩阵张量积生成的参数化酉演化。
6、问题哈密顿量可通过对根据问题信息构造的多个哈密顿量项求和或加权求和得到。各项分别表征问题信息的相应部分,组合后形成用于搜索的问题哈密顿量。
7、问题哈密顿量产生的演化及全局混合演化,可采用数字量子计算、模拟量子计算、数字-模拟混合量子计算、基于测量的量子计算中的一种或多种方式实现。全局混合演化的理论描述与设备的执行方式分别确定。
8、本发明还提供一种基于量子演化的搜索系统,包括量子计算设备或经典模拟计算设备。量子计算设备执行上述搜索方法;经典模拟计算设备对上述方法中的量子态制备、演化及测量进行数值模拟,并根据搜索条件确定搜索结果。量子计算设备可采用超导量子处理器、离子阱量子处理器、中性原子量子处理器、光量子处理器或基于ising相互作用的量子处理器中的一种或多种。
9、本发明还提供计算机可读存储介质及计算机程序产品。相应程序被处理器执行时,使量子计算设备执行上述方法,或者使经典模拟计算设备对其中的量子态制备、演化及测量进行数值模拟,并根据搜索条件确定搜索结果。
10、有益效果:
11、本发明通过全局混合演化与问题哈密顿量产生的演化配合,在初始态与目标态集合张成的目标子空间内形成相干叠加,为一般势能景观中的搜索提供量子演化途径。搜索条件可以对应一个或多个目标态,测量得到满足条件的对象即可确定相应搜索结果。
12、采用随机量子电路时,将已有的全局混合能力用于具有实际搜索目标的计算任务,为随机量子电路提供搜索用途。该搜索过程通过问题哈密顿量与全局混合演化的配合完成,无需将对该电路全部门参数的变分训练作为必经步骤。
13、在已有一般势能演化可供使用的场景中,直接利用该势能景观进行搜索,可减少为构造0/1势能而额外进行的目标判定、势能转换或相互作用重构。具体实施可结合不同量子设备的操作能力,并可在经典模拟计算设备上进行数值模拟。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com