基于量子算法的电力系统潮流计算

白林飞,郭奋卓

(北京邮电大学 理学院， 北京 100876)

在解决电力系统规划和运行中出现的各种问题时，电力系统潮流计算[1-3]发挥了巨大的作用.潮流计算是电力系统中非常重要的分析计算.一方面，潮流计算可以为电气设备的选择提供依据，优化供电方案;另一方面可以对运行中的电力系统进行静态安全分析和运行模式调整，也可以为电力系统故障计算和稳定性计算提供初始数据[4-5].电力系统是一个复杂的非线性系统，因此其中的潮流计算主要是求解非线性方程组.而非线性方程组的求解，一般会转化为多个线性方程组的求解来实现.现有最基础的潮流计算方法是牛顿-拉夫逊方法[6].文献[7-12]分别对牛顿-拉夫逊方法的雅可比矩阵进行了不同修改，进而提出了一系列类牛顿法.在本文中，将文献[6-12]中提出的方法统称为牛顿法.此后，学者们对区间潮流计算[13]和交直流潮流计算[14]也进行了研究.在使用牛顿法进行潮流计算时，通常需要求解节点导纳矩阵Y，有时也涉及到节点阻抗矩阵Z的求解.现有的经典方法求解Y阵和Z阵的时间复杂度都是指数级别的，对存储空间的要求也比较大.求解Y阵和Z阵的过程实际上是求解大型线性稀疏方程组.随着电力系统规模的增大，方程组系数矩阵的阶数越来越高.

求解线性方程组问题在信号处理、计算机科学和物理学等领域具有非常重要的地位. 这些领域涉及的数据级别一般非常大，对应线性方程组的未知数个数非常多. 经典算法求解高维线性方程组复杂度高. 量子计算为高速求解高维线性方程提供了新的思路.2009年，Harrow，Hassidim和Lloyd提出了求解线性方程组的高效量子算法(HHL算法)[15].在求解线性方程组Ax=b，其中A∈Rn×n且x,b∈R时，对于稀疏且条件良好的矩阵A，该算法时间复杂度为O(polylog(n)).此后，文献[16]又对HHL算法进行了改进，进一步降低了复杂度.由于哈密顿模拟[17-18]的限制，HHL算法并不适用于大部分稠密矩阵.文献[19]将块编码技术[20]应用到稠密矩阵的哈密顿模拟中，拓宽了HHL算法的适用范围.最近，Shao C，Xiang H又提出了不依赖于哈密顿模拟和相位估计[21]的量子迭代算法[22]来求解线性方程组，其复杂度为O(polylog(n)).

本文利用了量子算法来求解节点导纳矩阵Y和节点阻抗矩阵Z.节点导纳矩阵由节点电压方程导出，表示为YV=I，其中V矩阵代表每个节点的电压，I矩阵代表每个节点的注入电流，节点导纳矩阵的求解是利用已知的V和I来求解矩阵Y.为了使用HHL算法求解上述问题，我们首先将节点电压方程转换为VTYT=IT.然后将矩阵Y和I进行行分块，并通过矩阵方程分解将其分解成n个线性方程组VTyk=ik,k=1,…,n，其中yk={yk1,…,ykn}为矩阵Y的行向量.

最后直接用HHL算法求解线性方程组，就可以得到Y阵的信息.在此基础上，利用Z阵和Y阵互为逆矩阵这一特性，可以通过求解矩阵方程YZ=E来得到Z阵.文献[22]中提出的量子迭代算法，不仅可以直接利用上一步结果中得到的Y阵的行向量yk〉，而且与HHL算法相比，相对于给定误差有指数级别的加速.

为了使问题模型符合量子迭代算法，首先将Z阵和E阵进行列分块，并利用矩阵方程分解将上述问题转换为求解线性方程组Yzk=ek,k=1,…,n.然后直接用量子行迭代法来求解方程组即得到Z阵.与经典算法相比，使用量子算法求解Y阵和Z阵均实现了指数级加速.

1.1 线性方程组的经典算法

线性方程组的经典解法一般分为直接法和迭代法[23-24].

求解线性方程的直接法一般是对系数矩阵进行LU分解.根据LU分解方法的不同，线性方程组的直接解法也有不同的形式，其中最著名的是高斯消元法. 但是高效的直接法非常复杂，参数很多，需要具体问题具体分析.并且，对稀疏矩阵进行LU分解过程中会产生大量非零填充元素，因此直接法比系数矩阵需要更多的存储空间.

线性方程组的迭代解法也称为间接法.迭代法比与直接法相比需要更少的内存空间，迭代步数比较灵活，一旦满足精度要求即可停止，这在不需要精确求解线性方程组的环境中非常重要.但是迭代法收敛速度慢，有时甚至不收敛，所以电力系统潮流计算一般都使用直接法.

随着互联电网的出现，电力系统问题的求解规模不断扩大.在这种情况下，使用直接法求解大规模稀疏线性方程组是不切实际的，因为LU分解非常耗时. 一般来说，直接法求解稠密矩阵的时间复杂度为O(n3)，求解稀疏矩阵的时间复杂度介于O(n1.6)和O(n1.7)之间.

1.2 线性方程组的量子算法

HHL算法[15]是求解线性方程组最常用的量子算法，其目标是制备一个与线性方程组Ax=b的解有关的量子态x〉.如果矩阵AN×N和N维向量b是稀疏的，对于恒定精度， 算法的复杂度是O(log(n)s2κ2/ε)，其中κ=‖A‖‖A-1‖是A的条件数，s是稀疏度，ε是精度.

电网是现代电力系统分析的基础，可以用节点导纳矩阵或节点阻抗矩阵来描述，这两种矩阵互为逆矩阵.本节将介绍如何使用量子算法求解节点阻抗和节点导纳矩阵.

节点导纳矩阵由节点电压方程导出，表示为YV=I，其中V中的元素表示各节点的电压，I中的元素代表每个节点的注入电流.

我们将上面的式子转化为VTYT=IT，令Y=(y1,…,yn)T,I=(i1,…,in)T,则矩阵乘积YV=I的求解就可以转化为对

VTyk=ik,k=1,…,n

的求解.

一般情况下，由于节点导纳矩阵的稀疏性，系数矩阵是稀疏的，所以我们可以使用HHL算法[15]来求解上面的线性方程组.

步骤2：执行相位估计操作，我们可以得到

步骤3：添加一个辅助量子态0〉后执行受控旋转操作得到

步骤4：执行相位估计逆操作，得到

步骤5：执行测量操作使得最后一个寄存器获得1〉的结果，得

由于节点阻抗矩阵Z阵是一个满秩矩阵，它比节点导纳矩阵Y包含更多的信息，但求解Z阵也比求解Y阵复杂得多.常用的求解Z矩阵的方法有支路追加法和Y阵求逆法[4].其中，Y阵求逆法是求解节点阻抗矩阵最基本的方法，最常用的是LDU三角分解法[23]，它源于高斯消元法，当线性方程组的维数较大时，算法的复杂度较高.

使用Y阵求逆法求节点阻抗矩阵本质上是求解矩阵方程YZ=E,如果我们将Z阵分解成Z=(z1,…,zn)，令E=(e1,…,en)，则上述问题可以转化成求解一系列线性方程组Yzk=ek,k=1,…,n.

在前面已经得到了Y矩阵的行向量，即yt〉可以被有效制备，我们可以直接使用量子行迭代法[22]来求解与Z相关的线性方程组.

下面介绍使用行迭代法求解线性方程组的具体过程.

步骤1：随机选择一个单位向量z0〉使得它能够被有效制备.令k=0，vk=1,则初始状态可以被表示为一般形式：

步骤4：令k=k+1，重复执行步骤2、3，直到收敛.

在步骤3中，

I2⊗(In-yt〉〈yt)+σx⊗yt〉〈yt

算子SWAPi,j表示将第i个量子位和第j个量子位进行交换.

使用HHL算法求解线性方程组的复杂度为O(log(n)s2κ2/ε，其中κ是矩阵A的条件数，s是稀疏度，ε是精度.求解Y阵至多需要求解n个线性方程组，因此其复杂度的上限为O(nlog(n)s2κ2/ε.在不考虑稀疏度和误差的情况下，其复杂度可表示为O(nlog(n)).一般来说，经典直接法求解稀疏矩阵的时间复杂度介于O(n1.6)和O(n1.7)之间.与经典算法中的直接求解相比，量子算法实现了指数加速.

如果我们想得到矩阵的所有信息，就需要借助量子层析来实现.根据文献[28]， 层析问题可以通过使用基于量子算法的量子层析来解决，其复杂度为O(log(n)s2κ2/ε).

求解节点阻抗矩阵和节点导纳矩阵是电力系统潮流计算中非常重要的一步，随着电力系统规模的增大，使用经典算法来求解该矩阵需要大量计算.本文将量子计算应用于电力系统分析计算，通过对电力系统线性方程组模型的一系列转化使其适用于量子算法模型，然后利用HHL算法和量子迭代算法来求解线性方程组，以得到所需矩阵的信息.通过量子层析技术，可以进一步得到矩阵的全部经典信息.与已有的经典方法相比，使用量子算法来解决电力系统潮流计算问题，其复杂度达到了指数级别的加速.如果能找到直接求解矩阵方程的量子算法，本文所得的潮流计算的时间复杂度有望得到进一步降低.