关键词:
量子计算
Z-特征值
黎曼二阶方法
瑞利商
几何测度
摘要:
量子计算是一种由量子力学发展而来的新的计算架构,与经典计算相比,量子计算针对特定问题的求解具有量子优越性。利用量子计算加速优化问题的求解产生的量子优化方法是近年来颇受关注的重要研究内容,其主要研究是如何利用量子算法降低优化算法的计算复杂度。
在量子系统中,单位向量可以通过振幅编码的方式编码为量子态,因此许多量子系统中的优化问题都是单位球流形上的优化问题。本文将从黎曼流形优化算法的角度出发,开展针对张量特征值问题的量子优化算法研究。研究方向包括计算张量Z-特征值问题的量子算法及经典优化方法的量子算法实现。但是碍于不可克隆原理,量子计算无法复制一个未知的量子态,同时也难以提取量子态中的振幅信息。因此亟需解决如何在量子优化算法中交互量子信息与经典信息,经典优化方法中的步长搜索及最优性准则的判别的量子实现等问题。另外,张量特征值优化算法的一个重要环节是内积计算,量子内积算法也是从量子信息提取经典信息的重要方式。目前计算复杂度较优的内积算法需要在计算前通过层析算法提取量子信息,该过程导致算法的复杂度过高。本文针对上述问题开展研究,主要研究内容与创新点如下:
1.针对内积计算问题,提出了一种无层析量子内积算法,并对算法进行了时间复杂度分析。无层析量子内积算法的核心思想是借鉴量子主成分分析方法主动提取量子信息,即一个量子系统的多个副本的密度算子可以用于构造该密度算子的哈密顿量演化。当其量子态为纯态且演化时间取为π时,则其哈密顿量演化等价于作用于其他量子态的反射算子。最后利用反射算子构造出Grover迭代,并对Grover迭代进行相位估计,从相位中得到内积的估计信息。无层析量子内积算法避免了层析再制备量子态的过程,将量子内积计算的时间复杂度从O(max{n,?-2})优化为O(?e-1?-1)。
2.针对张量Z-特征值问题,提出了求解该问题的黎曼阻尼牛顿方法,并设计了相应的量子算法降低其计算复杂度。由于经典张量代数运算复杂度会随张量数据的阶数增大而指数增长,为此,我们设计张量代数运算的量子数据结构和算法降低张量运算的复杂度。本文提出了一种量子黎曼阻尼牛顿混合算法,同时针对大规模线性方程组求解、最优性准则判别等问题分别采用了时间复杂度更优的量子算法;对于逻辑判别、状态更新等运算采用了经典算法;而提取量子信息为经典信息的过程,采用了两种提取方法:针对下降方向的量子信息提取采用层析算法来实现,针对判别搜索状态的量子信息采用了无层析的量子内积算法来提取。最后在相同的收敛条件下,将求解Z-特征值的算法复杂度从经典算法的O(nm?g-3/2)降低到混合量子算法的O([poly(m log n)μκ/?2+n2 log(n)]?g-3/2),实现了关于张量维度上的近似平方加速,在理想条件下甚至能达到多项式加速。
3.针对瑞利商问题,提出了利用量子态旋转实现的量子黎曼Barzilai-Borwein(BB)方法,对经典BB优化算法的量子实现进行了尝试。由于经典BB方法需要上一步与当前步的信息,而量子计算中前一步信息难以利用,这为该算法的量子实现带来了困难。另外,如何从振幅编码的量子态中构造梯度形式及如何对迭代中的量子态进行最优性判别也是我们面临的难题。为了克服上述困难,我们首先发现一类BB方法的迭代形式与量子优化中的量子态迭代形式一致。为此,我们构造了量子黎曼BB方法,核心思想在于通过量子态旋转实现优化迭代。最后,我们利用无层析量子内积算法和量子算术运算实现了量子黎曼BB算法,该算法可以保证算法终止时得到的结果满足最优性条件。