线性方程组求解方法、装置、介质及电子装置与流程

1.本发明属于量子计算技术领域，特别是涉及一种线性方程组求解方法、装置、介质及电子装置。


背景技术：

2.对线性系统组的求解是许多科学与工程问题的核心，求解此类问题的经典算法统称为线性系统算法。近年来，量子计算领域的一个非常重要的成果是量子线性系统算法，其中最著名的当属harrow、hassidim和lloyd于2009年共同提出的hhl算法，但是该算法随着输入矩阵条件数的增大，求解线性系统问题的复杂度会随之提高，导致量子求解线性系统问题加速效果消失。


技术实现要素：

3.本发明的目的是提供一种线性方程组求解方法、装置、介质及电子装置，旨在降低线性系统问题的复杂度，实现量子求解线性系统问题的加速效果。
4.本发明的一个实施例提供了一种线性方程组求解方法，所述方法包括：
5.获取线性方程组ax＝b中的矩阵a和向量b，所述x为未知量；
6.在所述矩阵a的条件数ka大于预设阈值时，通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
，所述矩阵a
′
的条件数ka′
小于所述矩阵a的条件数ka；
7.基于所述矩阵a
′
和所述向量b
′
构建的线性方程组a
′
x＝b
′
求解所述未知量x。
8.可选的，所述通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
，包括：
9.制备所述向量b的量子态|b》，以及基于多项式函数p(y)和所述矩阵a确定多项式p(a)，所述y为自变量；
10.基于所述多项式p(a)构建算符以及将所述多项式p(a)与所述矩阵a相乘，得到矩阵a
′
；
11.将所述算符作用在所述量子态|b》上，得到量子态|b
′
》，所述量子态|b
′
》为向量b
′
对应的量子态。
12.可选的，所述基于多项式函数p(y)和所述矩阵a确定多项式p(a)之前，所述方法还包括：
13.获取含参的近似函数km(y)，以及确定所述含参的近似函数km(y)的定义域；
14.从所述定义域中选取m+2个近似偏差点以及将所述m+2个近似偏差点代入所述含参的近似函数km(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组km(yk)-t＝(-1)
k+1
e，其中k＝0，1，2
…
m+1，所述m为大于0的整数，所述t为所述定义域中的任一个自然数；
15.求解所述线性方程组km(yk)-t＝(-1)
k+1
e，得到所述含参的近似函数km(y)中参数的取值；
16.基于所述参数的取值确定目标近似函数，以及基于所述目标近似函数确定所述多项式函数p(y)。
17.可选的，所述基于所述参数的取值确定目标近似函数，包括：
18.将所述参数的取值代入所述含参的近似函数km(y)中，得到初始近似函数；
19.确定所述初始近似函数与所述t之差的绝对值的极值点；
20.若所述极值点与所述m+2个近似偏差点在精度要求内相等，则将所述初始近似函数确定为目标近似函数；
21.若所述极值点与所述m+2个近似偏差点在精度要求内不相等，则将所述极值点作为新的所述m+2个近似偏差点，以及执行步骤所述将所述m+2个近似偏差点代入所述含参的近似函数km(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组km(yk)-t＝(-1)
k+1
e。
22.可选的，所述基于所述目标近似函数确定所述多项式函数p(y)，包括：
23.基于所述目标近似函数和所述多项式函数p(y)的关系式p(y)＝k(y)/f(y)确定所述多项式函数p(y)，所述f(y)＝y。
24.可选的，若所述含参的近似函数km(y)为奇函数，则所述km(y)＝若所述含参的近似函数km(y)为偶函数，则所述(y)为偶函数，则所述所述θ
2i
、θ
2i+1
为参数，所述i为大于或等于0的整数。
25.可选的，所述基于所述多项式p(a)构建算符包括：
26.通过量子信号处理qsp制备所述多项式p(a)对应的算符
27.可选的，所述基于所述矩阵a
′
和所述向量b
′
构建的线性方程组a
′
x＝b
′
求解所述未知量x，包括：
28.基于所述矩阵a确定hhl算法所需的算符
29.将所述向量b
′
对应的量子态|b
′
》和所述算符输入至所述hhl算法，确定包含所述未知量x取值的目标量子态；
30.基于所述目标量子态确定所述未知量x的求解结果。
31.可选的，所述基于所述矩阵a
′
确定hhl算法所需的算符包括：
32.确定hhl算法所需的算符
33.将所述算符按照雅可比-安格尔jacobi-anger展开式展开，确定所述算符的指数展开式，所述算符的指数展开式为：
[0034][0035]
其中，jk是k阶第一类贝塞尔函数，tk是k阶第一类契比雪夫多项式；
[0036]
保留q阶精度的所述算符的指数展开式，q阶精度的所述算符的指数展开式为：
[0037]eiγt
＝f1(γ，t)+f2(γ，t)，
[0038]
其中，
[0039][0040][0041]
γ＝p(a)a；
[0042]
通过所述qsp制备所述f1(γ,t)对应的算符和所述f2(γ,t)对应的算符
[0043]
通过酉操作线性合并lcu以及所述算符和所述算符构建所述算符
[0044]
本发明的又一实施例提供了一种线性方程组求解装置，所述装置包括：
[0045]
获取单元，用于获取线性方程组ax＝b中的矩阵a和向量b，所述x为未知量；
[0046]
处理单元，用于在所述矩阵a的条件数κa大于预设阈值时，通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
，所述矩阵a
′
的条件数κa′
小于所述矩阵a的条件数κa；
[0047]
计算单元，用于基于所述矩阵a
′
和所述向量b
′
构建新的线性方程组a
′
x＝b
′
求解所述未知量x。
[0048]
可选的，在所述通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
方面，所述处理单元具体用于：
[0049]
制备所述向量b的量子态|b》，以及基于多项式函数p(y)和所述矩阵a确定多项式p(a)，所述y为自变量；
[0050]
基于所述多项式p(a)构建算符以及将所述多项式p(a)与所述矩阵a相乘，得到矩阵a
′
；
[0051]
将所述算符作用在所述量子态|b》上，得到量子态|b
′
》，所述量子态|b
′
》为向量b
′
对应的量子态。
[0052]
可选的，在所述基于多项式函数p(y)和所述矩阵a确定多项式p(a)之前，所述处理单元还用于：
[0053]
获取含参的近似函数km(y)，以及确定所述含参的近似函数km(y)的定义域；
[0054]
从所述定义域中选取m+2个近似偏差点以及将所述m+2个近似偏差点代入所述含参的近似函数km(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组km(yk)-t＝(-1)
k+1
e，其中k＝0，1，2
…
m+1，所述m为大于0的整数，所述t为所述定义域中的任一个自然数；
[0055]
求解所述线性方程组km(yk)-t＝(-1)
k+1
e，得到所述含参的近似函数km(y)中参数的取值；
[0056]
基于所述参数的取值确定目标近似函数，以及基于所述目标近似函数确定所述多项式函数p(y)。
[0057]
可选的，在所述基于所述参数的取值确定目标近似函数方面，所述处理单元具体用于：
[0058]
将所述参数的取值代入所述含参的近似函数km(y)中，得到初始近似函数；
[0059]
确定所述初始近似函数与所述t之差的绝对值的极值点；
[0060]
若所述极值点与所述m+2个近似偏差点在精度要求内相等，则将所述初始近似函
数确定为目标近似函数；
[0061]
若所述极值点与所述m+2个近似偏差点在精度要求内不相等，则将所述极值点作为新的所述m+2个近似偏差点，以及执行步骤所述将所述m+2个近似偏差点代入所述含参的近似函数km(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组km(yk)-t＝(-1)
k+1
e。
[0062]
可选的，在所述基于所述目标近似函数确定所述多项式函数p(y)方面，所述处理单元具体用于：
[0063]
基于所述目标近似函数和所述多项式函数p(y)的关系式p(y)＝k(y)/f(y)确定所述多项式函数p(y)，所述f(y)＝y。
[0064]
可选的，若所述含参的近似函数km(y)为奇函数，则所述(y)为奇函数，则所述若所述含参的近似函数km(y)为偶函数，则所述(y)为偶函数，则所述所述θ
2i
、θ
2i+1
为参数，所述i为大于或等于0的整数。
[0065]
可选的，在所述基于所述多项式p(a)构建算符方面，所述处理单元具体用于：
[0066]
通过量子信号处理qsp制备所述多项式p(a)对应的算符
[0067]
可选的，在所述基于所述矩阵a
′
和所述向量b
′
构建的线性方程组a
′
x＝b
′
求解所述未知量x方面，所述计算单元具体用于：
[0068]
基于所述矩阵a
′
确定hhl算法所需的算符
[0069]
将所述向量b
′
对应的量子态|b
′
》和所述算符输入至所述hhl算法，确定包含所述未知量x取值的目标量子态；
[0070]
基于所述目标量子态确定所述未知量x的求解结果。
[0071]
可选的，在所述基于所述矩阵a
′
确定hhl算法所需的算符方面，所述计算单元具体用于：
[0072]
确定hhl算法所需的算符
[0073]
将所述算符按照雅可比-安格尔jacobi-anger展开式展开，确定所述算符的指数展开式，所述算符的指数展开式为：
[0074][0075]
其中，jk是k阶第一类贝塞尔函数，tk是k阶第一类契比雪夫多项式；
[0076]
保留q阶精度的所述算符的指数展开式，q阶精度的所述算符的指数展开式为：
[0077]eiγt
＝f1(γ，t)+f2(γ，t)，
[0078]
其中，
[0079][0080][0081]
γ＝p(a)a；
[0082]
通过所述qsp制备所述f1(γ,t)对应的算符和所述f2(γ,t)对应的算符
[0083]
通过酉操作线性合并lcu以及所述算符和所述算符构建所述算符
[0084]
本发明的又一实施例提供了一种存储介质，所述存储介质中存储有计算机程序，其中，所述计算机程序被设置为运行时执行上述任一项中所述的方法。
[0085]
本发明的又一实施例提供了一种电子装置，包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行上述任一项中所述的方法。
[0086]
与现有技术相比，本发明提供的一种线性方程组求解方法，通过多项式预处理器对原线性方程组ax＝b中的矩阵a和向量b进行处理，以得到新的线性方程组a
′
x＝b
′
，新的线性方程组中的矩阵a
′
的条件数κa′
小于原线性方程组中的矩阵a的条件数κa，从而降低了输入矩阵的条件数，进而降低了线性系统问题的复杂度，然后再对新的线性方程组进行求解，得到共同的未知量x，从而实现了量子求解线性系统问题的加速效果。
附图说明
[0087]
图1为本发明实施例提供的一种线性方程组求解方法的计算机终端的硬件结构框图；
[0088]
图2为本发明实施例提供的一种线性方程组求解方法的流程示意图；
[0089]
图3为本发明实施例提供的一种构建算符的量子线路图；
[0090]
图4为本发明实施例提供的一种线性方程组求解装置的结构示意图。
具体实施方式
[0091]
下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。
[0092]
本发明实施例首先提供了一种线性方程组求解方法，该方法可以应用于电子设备，如计算机终端，具体如普通电脑、量子计算机等。
[0093]
下面以运行在计算机终端上为例对其进行详细说明。图1为本发明实施例提供的一种线性方程组求解方法的计算机终端的硬件结构框图。如图1所示，计算机终端可以包括一个或多个(图1中仅示出一个)处理器102(处理器102可以包括但不限于微处理器mcu或可编程逻辑器件fpga等的处理装置)和用于存储线性方程组求解方法的存储器104，可选地，上述计算机终端还可以包括用于通信功能的传输装置106以及输入输出设备108。本领域普通技术人员可以理解，图1所示的结构仅为示意，其并不对上述计算机终端的结构造成限定。例如，计算机终端还可包括比图1中所示更多或者更少的组件，或者具有与图1所示不同的配置。
[0094]
存储器104可用于存储应用软件的软件程序以及模块，如本发明实施例中的线性方程组求解方法对应的程序指令/模块，处理器102通过运行存储在存储器104内的软件程序以及模块，从而执行各种功能应用以及数据处理，即实现上述的方法。存储器104可包括高速随机存储器，还可包括非易失性存储器，如一个或者多个磁性存储装置、闪存、或者其
他非易失性固态存储器。在一些实例中，存储器104可进一步包括相对于处理器102远程设置的存储器，这些远程存储器可以通过网络连接至计算机终端。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
[0095]
传输装置106用于经由一个网络接收或者发送数据。上述的网络具体实例可包括计算机终端的通信供应商提供的无线网络。在一个实例中，传输装置106包括一个网络适配器(network interface controller，nic)，其可通过基站与其他网络设备相连从而可与互联网进行通讯。在一个实例中，传输装置106可以为射频(radio frequency，rf)模块，其用于通过无线方式与互联网进行通讯。
[0096]
需要说明的是，真正的量子计算机是混合结构的，它包含两大部分：一部分是经典计算机，负责执行经典计算与控制；另一部分是量子设备，负责运行量子程序进而实现量子计算。而量子程序是由量子语言如qrunes语言编写的一串能够在量子计算机上运行的指令序列，实现了对量子逻辑门操作的支持，并最终实现量子计算。具体的说，量子程序就是一系列按照一定时序操作量子逻辑门的指令序列。
[0097]
在实际应用中，因受限于量子设备硬件的发展，通常需要进行量子计算模拟以验证量子算法、量子应用等等。量子计算模拟即借助普通计算机的资源搭建的虚拟架构(即量子虚拟机)实现特定问题对应的量子程序的模拟运行的过程。通常，需要构建特定问题对应的量子程序。本发明实施例所指量子程序，即是经典语言编写的表征量子比特及其演化的程序，其中与量子计算相关的量子比特、量子逻辑门等等均有相应的经典代码表示。
[0098]
量子线路作为量子程序的一种体现方式，也称量子逻辑电路，是最常用的通用量子计算模型，表示在抽象概念下对于量子比特进行操作的线路，其组成包括量子比特、线路(时间线)、以及各种量子逻辑门，最后常需要通过量子测量操作将结果读取出来。
[0099]
不同于传统电路是用金属线所连接以传递电压信号或电流信号，在量子线路中，线路可看成是由时间所连接，亦即量子比特的状态随着时间自然演化，在这过程中按照哈密顿运算符的指示，一直到遇上逻辑门而被操作。
[0100]
一个量子程序整体上对应有一条总的量子线路，本发明所述量子程序即指该条总的量子线路，其中，该总的量子线路中的量子比特总数与量子程序的量子比特总数相同。可以理解为：一个量子程序可以由量子线路、针对量子线路中量子比特的测量操作、保存测量结果的寄存器及控制流节点(跳转指令)组成，一条量子线路可以包含几十上百个甚至成千上万个量子逻辑门操作。量子程序的执行过程，就是对所有的量子逻辑门按照一定时序执行的过程。需要说明的是，时序即单个量子逻辑门被执行的时间顺序。
[0101]
需要说明的是，经典计算中，最基本的单元是比特，而最基本的控制模式是逻辑门，可以通过逻辑门的组合来达到控制电路的目的。类似地，处理量子比特的方式就是量子逻辑门。使用量子逻辑门，能够使量子态发生演化，量子逻辑门是构成量子线路的基础，量子逻辑门包括单比特量子逻辑门，如hadamard门(h门，阿达马门)、泡利-x门(x门)、泡利-y门(y门)、泡利-z门(z门)、rx门、ry门、rz门等等；多比特量子逻辑门，如cnot门、cr门、iswap门、toffoli门等等。量子逻辑门一般使用酉矩阵表示，而酉矩阵不仅是矩阵形式，也是一种操作和变换。一般量子逻辑门在量子态上的作用是通过酉矩阵左乘以量子态右矢对应的矩阵进行计算。
[0102]
参见图2，图2为本发明实施例提供的一种线性方程组求解方法的流程示意图。可
以包括如下步骤：
[0103]
步骤201：获取线性方程组ax＝b中的矩阵a和向量b，所述x为未知量；
[0104]
在应用数学和科学工程计算领域，许多问题的数学模型都可以用线性方程组来描述。例如目标电磁特性仿真计算问题经由矩量法、有限元等数值算法离散化电磁场微积分方程即转化为了对矩阵方程的求解，又如流体力学中的ns方程求解、量子色动力学(qcd)中的格点规范理论等。
[0105]
线性系统是一种数学模型，是指用线性算子组成的系统，且同时满足叠加性与均匀性(又称为齐次性)的系统，目前，线性系统是很多科学和工程领域的核心。对于待处理线性系统的线性方程组ax＝b分别获取矩阵a和向量b的元素信息及维数，其中矩阵a，可以为系数矩阵，系数矩阵是矩阵中的众多类型之一，简单来说系数矩阵就是将线性方程组的系数组成矩阵来计算方程组的解x，系数矩阵常常用来表示一些项目的数学关系。
[0106]
步骤202：在所述矩阵a的条件数κa大于预设阈值时，通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
，所述矩阵a
′
的条件数κa′
小于所述矩阵a的条件数ka；
[0107]
在数值分析和线性代数中，矩阵a的条件数κa定义为：
[0108]
ka＝||a||||a-1
||
[0109]
其中，||a||、||a-1
||分别为矩阵a的范数和矩阵a的逆矩阵的范数。
[0110]
矩阵的条件数描述了矩阵对向量的拉伸能力和压缩能力，矩阵的条件数越大，求解线性系统问题的复杂度也会随之提高，导致采用量子求解线性系统问题加速的效果也会消失，因此为了实现线性系统问题的求解性能远超普通量子求解器，需要采用预处理器对矩阵a和向量b进行处理，降低矩阵的条件数，本发明实施例采用的预处理器为多项式预处理器。
[0111]
预设阈值可以是1、10、100、1000、10000，或是其他值，在此不做限定。
[0112]
步骤303：基于所述矩阵a
′
和所述向量b
′
构建新的线性方程组a
′
x＝b
′
求解所述未知量x。
[0113]
在通过多项式预处理器对矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
之后，其中矩阵a
′
的条件数κa′
小于矩阵a的条件数κa，即可采用普通的量子求解器求解矩阵a
′
和向量b
′
构建新的线性方程组a
′
x＝b
′
中的未知量x。
[0114]
与现有技术相比，本发明提供的一种线性方程组求解方法，通过多项式预处理器对原线性方程组ax＝b中的矩阵a和向量b进行处理，以得到新的线性方程组a
′
x＝b
′
，新的线性方程组中的矩阵a
′
的条件数κa′
小于原线性方程组中的矩阵a的条件数κa，从而降低了输入矩阵的条件数，进而降低了线性系统问题的复杂度，然后再对新的线性方程组进行求解，得到共同的未知量x，从而实现了量子求解线性系统问题的加速效果。
[0115]
在本发明提供的一具体实施例中，在所述通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
方面，包括：
[0116]
步骤2021：制备所述向量b的量子态|b》，以及基于多项式函数p(y)和所述矩阵a确定多项式p(a)，所述y为自变量；
[0117]
步骤2022：基于所述多项式p(a)构建算符以及将所述多项式p(a)与所述矩阵a相乘，得到矩阵a
′
；
[0118]
步骤2023：将所述算符作用在所述量子态|b》上，得到量子态|b
′
》，所述量子态|b
′
》为向量b
′
对应的量子态。
[0119]
其中，量子态所述n为向量b的维度。算符作用在量子态|b》上，得到量子态|b
′
》，量子态
[0120]
进一步的，在所述基于多项式函数p(y)和所述矩阵a确定多项式p(a)之前，所述方法还包括：
[0121]
步骤2023：获取含参的近似函数km(y)，以及确定所述含参的近似函数km(y)的定义域；
[0122]
步骤2024：从所述定义域中选取m+2个近似偏差点以及将所述m+2个近似偏差点代入所述含参的近似函数km(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组km(yk)-t＝(-1)
k+1
e，其中k＝0，1，2
…
m+1，所述m为大于0的整数，所述t为所述定义域中的任一个自然数；
[0123]
步骤2025：求解所述线性方程组km(yk)-t＝(-1)
k+1
e，得到所述含参的近似函数km(y)中参数的取值；
[0124]
步骤2026：基于所述参数的取值确定目标近似函数；
[0125]
步骤2027：基于所述目标近似函数确定所述多项式函数p(y)。
[0126]
其中，若所述含参的近似函数km(y)为奇函数，则所述(y)为奇函数，则所述若所述含参的近似函数km(y)为偶函数，则所述(y)为偶函数，则所述所述θ
2i
、θ
2i+1
为参数，所述i为大于或等于0的整数。这里，我们以含参的近似函数km(y)为偶函数为例。
[0127]
其中，所述含参的近似函数km(y)的定义域s＝[-|λa|
max
，-|λa|
min
]∪[|λa|
min
，|λa|
max
]，|λa|
max
为矩阵a的特征值的绝对值的最大值，|λa|
min
为矩阵a的特征值的绝对值的最小值。其中，m+2个近似偏差点的大小关系为：y0＜y1＜
…
＜ym＜y
m+1
，可以是等差排列，也可以不是等差排列，在此不做限定。
[0128]
其中，m+2维线性方程组km(yk)-t＝(-1)
k+1
e可以求解出m+2个未知数e、θ
2i
，i＝0，1，2
…
m。
[0129]
其中，含参的近似函数km(y)和偏差幅值e组成的关系式可以是km(yk)-t＝(-1)
k+1
e，也可以是km(yk)-t＝(-1)ke，两者求解出来的e符号相反。
[0130]
具体的，在所述基于所述参数的取值确定目标近似函数方面，包括：
[0131]
步骤2026a：将所述参数的取值代入所述含参的近似函数km(y)中，得到初始近似函数；
[0132]
步骤2026b：确定所述初始近似函数与所述t之差的绝对值的极值点；
[0133]
步骤2026c：若所述极值点与所述m+2个近似偏差点在精度要求内相等，则将所述初始近似函数确定为目标近似函数；
[0134]
步骤2026d：若所述极值点与所述m+2个近似偏差点在精度要求内不相等，则将所述极值点作为新的所述m+2个近似偏差点，以及执行步骤所述将所述m+2个近似偏差点代入所述含参的近似函数km(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组km(yk)-t＝(-1)
k+1
e。
[0135]
其中，精度要求例如可以是小数点后三位相同，如果极值点与其对应的近似偏差点的小数点后三位相同，则确定两者在精度要求内相等，当然不限定为小数点后三位，还可以是小数点前一位、后两位、后五位、后七位，或是其他值，在此不做限定。
[0136]
具体的，在所述基于所述目标近似函数确定所述多项式函数p(y)方面，包括：
[0137]
步骤2027a：基于所述目标近似函数和所述多项式函数p(y)的关系式p(y)＝k(y)/f(y)确定所述多项式函数p(y)。
[0138]
具体的，在所述基于所述多项式p(a)构建算符方面，包括：
[0139]
步骤2021a：通过量子信号处理qsp制备所述多项式p(a)对应的算符
[0140]
其中，量子信号处理(quantum signal processing，qsp)保证了定义在实数域上的多项式映射的量子算符是可以被制备的，当且仅当多项式为奇函数或偶函数时(即多项式为全奇数阶或者全偶数阶)。
[0141]
在本发明提供的一具体实施例中，所述基于所述矩阵a
′
和所述向量b
′
构建的线性方程组a
′
x＝b
′
求解所述未知量x，包括：
[0142]
步骤2031：基于所述矩阵a
′
确定hhl算法所需的算符
[0143]
步骤2032将所述向量b
′
对应的量子态|b
′
》和所述算符输入至所述hhl算法，确定包含所述未知量x取值的目标量子态；
[0144]
步骤2033：基于所述目标量子态确定所述未知量x的求解结果。
[0145]
具体的，在所述基于所述矩阵a
′
确定hhl算法所需的算符方面，包括：
[0146]
步骤2031a：确定hhl所需的算符
[0147]
步骤2031b:将所述算符按照雅可比-安格尔jacobi-anger展开式展开，确定所述算符的指数展开式，所述算符的指数展开式为：
[0148][0149]
其中，jk是k阶第一类贝塞尔函数，tk是k阶第一类契比雪夫多项式；
[0150]
步骤2031c：保留q阶精度的所述算符的指数展开式，q阶精度的所述算符的指数展开式为：
[0151]eiγt
＝f1(γ，t)+f2(γ，t)，
[0152]
其中，
[0153][0154][0155]
γ＝p(a)a；
[0156]
步骤2031d：通过所述qsp制备所述f1(γ,t)对应的算符和所述f2(γ,t)对应的算符
[0157]
步骤2031e：通过酉操作线性合并lcu以及所述算符和所述算符构建所述算符
[0158]
其中，当k是正整数时有jk(-x)＝(-1)
kjk
(x)，tk(-x)＝(-1)ktk(x)，因此f1(γ,t)为偶函数，f2(γ,t)为奇函数。因此算符同样能够通过qsp被制备。当制备得到算符后，可以通过酉操作线性合并(linear combination of unitary operators，lcu)构建算符如图3所示，图3为本发明实施例提供的一种构建算符的量子线路图。
[0159]
通过这种方式构建的成功率为η，经过振幅估计和振幅放大，成功率可以被放大到η≈1。在后续qpe过程中会出现o(-log∈)个受控门，整个过程成功率为其中δ＝logη。因此当η趋近1时，整个算法过程接近1。
[0160]
具体的，在所述将所述向量b
′
对应的量子态|b
′
＞和所述算符输入至所述hhl算法，确定包含所述未知量x取值的目标量子态方面，包括：
[0161]
步骤2032a：制备量子态|b
′
》；
[0162]
步骤2032b：通过量子相位估计qpe操作和受控旋转操作将所述初始量子态演化至包含所述未知量x取值的目标量子态，其中，所述qpe中所需的量子逻辑门为所述具体地，hhl算法需要三个寄存器，每个寄存器包括至少一个量子比特。在执行hhl算法之前，需要对三个寄存器初始化，即将三个寄存器中的量子比特均初始化为|0》。然后通过通用的方法将第三个寄存器的|0》转化为向量b的量子态|b》，再通过步骤2023：将所述算符作用在所述量子态|b》上，得到量子态|b
′
＞，其中，所述量子态
[0163]
在hhl算法中，量子相位估计(quantum phase estimation，qpe)操作具体为依次通过h门作用于第二寄存器，受控u门作用于第二寄存器和第三寄存器，门作用于第二寄存器，ft门为傅里叶变换对应的量子逻辑门。通过qpe操作将所述量子态演化至量子态其中为qpe得到的特征值λi的估计值；
[0164]
受控操作具体为将受控r门作用于第一寄存器和第二寄存器，第二寄存器为控制位，第一寄存器为受控位，通过所述量子态的子量子态对所述辅助比特的量子态执行受控旋转操作，得到量子态
[0165]
对所述第一寄存器进行测量，当所述第一寄存器的量子态为|1》时，得到量子态
[0166]
通过逆qpe操作将所述量子态演化至包含所述未知
量x取值的目标量子态
[0167]
具体的，基于所述目标量子态确定所述未知量x的求解结果，即未知量x取值为
[0168]
经过实际验证，本发明实施例提供的包括多项式预处理器的线性方程组求解方法对矩阵a条件数ka的优化倍数为即条件数优化倍数与所输入的多项式pm的阶数呈线性关系。整体求解复杂度为o(ls2κa′2logn)，相比于hhl求解复杂度o(s2k
a2
logn)，优化度为可见，随着l增大，优化程度线性提高。当l
→
o(κa)时，κa′
→
1，此时本发明实施例提供的包括多项式预处理器的线性方程组求解方法求解复杂度降至最低o(s2κalogn)。
[0169]
参见图4，图4为本发明实施例提供的一种线性方程组求解装置的结构示意图，与图2所示的流程相对应，可以包括：
[0170]
获取单元401，用于获取线性方程组ax＝b中的矩阵a和向量b，所述x为未知量；
[0171]
处理单元402，用于在所述矩阵a的条件数κa大于预设阈值时，通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
，所述矩阵a
′
的条件数κa′
小于所述矩阵a的条件数ka；
[0172]
计算单元403，用于基于所述矩阵a
′
和所述向量b
′
构建新的线性方程组a
′
x＝b
′
求解所述未知量x。
[0173]
可选的，在所述通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
方面，所述处理单元402具体用于：
[0174]
制备所述向量b的量子态|b》，以及基于多项式函数p(y)和所述矩阵a确定多项式p(a)，所述y为自变量；
[0175]
基于所述多项式p(a)构建算符以及将所述多项式p(a)与所述矩阵a相乘，得到矩阵a
′
；
[0176]
将所述算符作用在所述量子态|b》上，得到量子态|b
′
》，所述量子态|b
′
》为向量b
′
对应的量子态。
[0177]
可选的，在所述基于多项式函数p(y)和所述矩阵a确定多项式p(a)之前，所述处理单元402还用于：
[0178]
获取含参的近似函数km(y)，以及确定所述含参的近似函数km(y)的定义域；
[0179]
从所述定义域中选取m+2个近似偏差点以及将所述m+2个近似偏差点代入所述含参的近似函数km(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组km(yk)-t＝(-1)
k+1
e，其中k＝0，1，2
…
m+1，所述m为大于0的整数，所述t为所述定义域中的任一个自然数；
[0180]
求解所述线性方程组km(yk)-t＝(-1)
k+1
e，得到所述含参的近似函数km(y)中参数的取值；
[0181]
基于所述参数的取值确定目标近似函数，以及基于所述目标近似函数确定所述多
项式函数p(y)。
[0182]
可选的，在所述基于所述参数的取值确定目标近似函数方面，所述处理单元402具体用于：
[0183]
将所述参数的取值代入所述含参的近似函数km(y)中，得到初始近似函数；
[0184]
确定所述初始近似函数与所述t之差的绝对值的极值点；
[0185]
若所述极值点与所述m+2个近似偏差点在精度要求内相等，则将所述初始近似函数确定为目标近似函数；
[0186]
若所述极值点与所述m+2个近似偏差点在精度要求内不相等，则将所述极值点作为新的所述m+2个近似偏差点，以及执行步骤所述将所述m+2个近似偏差点代入所述含参的近似函数km(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组km(yk)-t＝(-1)
k+1
e。
[0187]
可选的，在所述基于所述目标近似函数确定所述多项式函数p(y)方面，所述处理单元402具体用于：
[0188]
基于所述目标近似函数和所述多项式函数p(y)的关系式p(y)＝k(y)/f(y)确定所述多项式函数p(y)，所述f(y)＝y||λa||
max
，其中，所述||λa||
max
为所述矩阵a的最大特征值的范数。
[0189]
可选的，若所述含参的近似函数km(y)为奇函数，则所述(y)为奇函数，则所述若所述含参的近似函数km(y)为偶函数，则所述(y)为偶函数，则所述所述θ
2i
、θ
2i+1
为参数，所述i为大于或等于0的整数。
[0190]
可选的，在所述基于所述多项式p(a)构建算符方面，所述处理单元402具体用于：
[0191]
将所述矩阵a赋值给所述自变量y，得到多项式p(a)；
[0192]
通过量子信号处理qsp制备所述多项式p(a)对应的算符
[0193]
可选的，在所述基于所述矩阵a
′
和所述向量b
′
构建的线性方程组a
′
x＝b
′
求解所述未知量x方面，所述计算单元403具体用于：
[0194]
基于所述矩阵a
′
确定hhl算法所需的算符
[0195]
将所述向量b
′
对应的量子态|b
′
》和所述算符输入至所述hhl算法，确定包含所述未知量x取值的目标量子态；
[0196]
基于所述目标量子态确定所述未知量x的求解结果。
[0197]
可选的，在所述基于所述矩阵a
′
确定hhl算法所需的算符方面，所述计算单元403具体用于：
[0198]
确定hhl算法所需的算符
[0199]
将所述算符按照雅可比-安格尔jacobi-anger展开式展开，确定所述算符的指数展开式，所述算符的指数展开式为：
[0200][0201]
其中，jk是k阶第一类贝塞尔函数，tk是k阶第一类契比雪夫多项式；
[0202]
保留q阶精度的所述算符的指数展开式，q阶精度的所述算符的指数展开式为：
[0203]eiγt
＝f1(γ，t)+f2(γ，t)，
[0204]
其中，
[0205][0206][0207]
γ＝p(a)a；
[0208]
通过所述qsp制备所述f1(γ,t)对应的算符和所述f2(γ,t)对应的算符
[0209]
通过酉操作线性合并lcu以及所述算符和所述算符构建所述算符
[0210]
本发明实施例还提供了一种存储介质，所述存储介质中存储有计算机程序，其中，所述计算机程序被设置为运行时执行上述任一项中方法实施例中的步骤。
[0211]
具体的，在本实施例中，上述存储介质可以被设置为存储用于执行以下步骤的计算机程序：
[0212]
获取线性方程组ax＝b中的矩阵a和向量b，所述x为未知量；
[0213]
在所述矩阵a的条件数κa大于预设阈值时，通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a和向量b
′
，所述矩阵a
′
的条件数κa′
小于所述矩阵a的条件数κa；
[0214]
基于所述矩阵a
′
和所述向量b
′
构建新的线性方程组a
′
x＝b求解所述未知量x。
[0215]
具体的，在本实施例中，上述存储介质可以包括但不限于：u盘、只读存储器(read-only memory，简称为rom)、随机存取存储器(random access memory，简称为ram)、移动硬盘、磁碟或者光盘等各种可以存储计算机程序的介质。
[0216]
本发明的再一实施例还提供了一种电子装置，包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行上述任一项中方法实施例中的步骤。
[0217]
具体的，上述电子装置还可以包括传输设备以及输入输出设备，其中，该传输设备和上述处理器连接，该输入输出设备和上述处理器连接。
[0218]
具体的，在本实施例中，上述处理器可以被设置为通过计算机程序执行以下步骤：
[0219]
获取线性方程组ax＝b中的矩阵a和向量b，所述x为未知量；
[0220]
在所述矩阵a的条件数κa大于预设阈值时，通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
，所述矩阵a
′
的条件数κa′
小于所述矩阵a的条件数κa；
[0221]
基于所述矩阵a
′
和所述向量b
′
构建新的线性方程组a
′
x＝b
′
求解所述未知量x。
[0222]
以上依据图式所示的实施例详细说明了本发明的构造、特征及作用效果，以上所述仅为本发明的较佳实施例，但本发明不以图面所示限定实施范围，凡是依照本发明的构想所作的改变，或修改为等同变化的等效实施例，仍未超出说明书与图示所涵盖的精神时，均应在本发明的保护范围内。

技术特征：
1.一种线性方程组求解方法，其特征在于，所述方法包括：获取线性方程组ax＝b中的矩阵a和向量b，所述x为未知量；在所述矩阵a的条件数κ
a
大于预设阈值时，通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
，所述矩阵a
′
的条件数k
a
′
小于所述矩阵a的条件数κ
a
；基于所述矩阵a
′
和所述向量b
′
构建新的线性方程组a
′
x＝b
′
求解所述未知量x。2.如权利要求1所述的方法，其特征在于，所述通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
，包括：制备所述向量b的量子态|b>，以及基于多项式函数p(y)和所述矩阵a确定多项式p(a)，所述y为自变量；基于所述多项式p(a)构建算符以及将所述多项式p(a)与所述矩阵a相乘，得到矩阵a
′
；将所述算符作用在所述量子态|b>上，得到量子态|b
′
>，所述量子态|b
′
>为向量b
′
对应的量子态。3.如权利要求2所述的方法，其特征在于，所述基于多项式函数p(y)和所述矩阵a确定多项式p(a)之前，所述方法还包括：获取含参的近似函数k
m
(y)，以及确定所述含参的近似函数k
m
(y)的定义域；从所述定义域中选取m+2个近似偏差点以及将所述m+2个近似偏差点代入所述含参的近似函数k
m
(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组k
m
(y
k
)-t＝(-1)
k+1
e，其中k＝0,1,2
···
m+1，所述m为大于0的整数，所述t为所述定义域中的任一个自然数；求解所述线性方程组k
m
(y
k
)-t＝(-1)
k+1
e，得到所述含参的近似函数k
m
(y)中参数的取值；基于所述参数的取值确定目标近似函数，以及基于所述目标近似函数确定所述多项式函数p(y)。4.如权利要求3所述的方法，其特征在于，所述基于所述参数的取值确定目标近似函数，包括：将所述参数的取值代入所述含参的近似函数k
m
(y)中，得到初始近似函数；确定所述初始近似函数与所述t之差的绝对值的极值点；若所述极值点与所述m+2个近似偏差点在精度要求内相等，则将所述初始近似函数确定为目标近似函数；若所述极值点与所述m+2个近似偏差点在精度要求内不相等，则将所述极值点作为新的所述m+2个近似偏差点，以及执行步骤所述将所述m+2个近似偏差点代入所述含参的近似函数k
m
(y)和偏差幅值e组成的关系式中，得到m+2维线性方程组k
m
(y
k
)-t＝(-1)
k+1
e。5.如权利要求3所述的方法，其特征在于，所述基于所述目标近似函数确定所述多项式函数p(y)，包括：基于所述目标近似函数和所述多项式函数p(y)的关系式p(y)＝k(y)/f(y)确定所述多项式函数p(y)，所述f(y)＝y。6.如权利要求3-5任一项所述的方法，其特征在于，若所述含参的近似函数k
m
(y)为奇函数，则所述若所述含参的近似函数k
m
(y)为偶函数，则所述
所述θ
2i
、θ
2i+1
为参数，所述i为大于或等于0的整数。7.如权利要求2所述的方法，其特征在于，所述基于所述多项式p(a)构建算符包括：通过量子信号处理qsp制备所述多项式p(a)对应的算符8.如权利要求7所述的方法，其特征在于，所述基于所述矩阵a
′
和所述向量b
′
构建的线性方程组a
′
x＝b
′
求解所述未知量x，包括：基于所述矩阵a
′
确定hhl算法所需的算符将所述向量b
′
对应的量子态|b
′
>和所述算符输入至所述hhl算法，确定包含所述未知量x取值的目标量子态；基于所述目标量子态确定所述未知量x的求解结果。9.如权利要求8所述的方法，其特征在于，所述基于所述矩阵a
′
确定hhl算法所需的算符包括：确定hhl算法所需的算符将所述算符按照雅可比-安格尔jacobi-anger展开式展开，确定所述算符的指数展开式，所述算符的指数展开式为：其中，j
k
是k阶第一类贝塞尔函数，t
k
是k阶第一类契比雪夫多项式；保留q阶精度的所述算符的指数展开式，q阶精度的所述算符的指数展开式为：e
iγt
＝f1(γ,t)+f2(γ,t)，其中，其中，γ＝p(a)a；通过所述qsp制备所述f1(γ,t)对应的算符和所述f2(γ,t)对应的算符通过酉操作线性合并lcu以及所述算符和所述算符构建所述算符10.一种线性方程组求解装置，其特征在于，所述装置包括：获取单元，用于获取线性方程组ax＝b中的矩阵a和向量b，所述x为未知量；处理单元，用于在所述矩阵a的条件数κ
a
大于预设阈值时，通过多项式预处理器对所述矩阵a和向量b进行处理，得到矩阵a
′
和向量b
′
，所述矩阵a
′
的条件数κ
a
′
小于所述矩阵a的条件数κ
a
；计算单元，用于基于所述矩阵a
′
和所述向量b
′
构建新的线性方程组a
′
x＝b
′
求解所述未知量x。11.一种存储介质，其特征在于，所述存储介质中存储有计算机程序，其中，所述计算机程序被设置为运行时执行所述权利要求1至9任一项中所述的方法。
12.一种电子装置，包括存储器和处理器，其特征在于，所述存储器中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行所述权利要求1至9任一项中所述的方法。

技术总结
本发明公开了一种线性方程组求解方法、装置、介质及电子装置，本发明通过多项式预处理器对原线性方程组Ax＝b中的矩阵A和向量b进行处理，以得到新的线性方程组A


技术研发人员：李叶 安宁波 窦猛汉
受保护的技术使用者：本源量子计算科技（合肥）股份有限公司
技术研发日：2021.12.03
技术公布日：2023/7/11