量子近似优化算法在最大独立集中的应用

最大独立集问题是著名的NP问题,并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题,提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型,推导出最大独立集问题的哈密顿量表达式;设计了基于量子近似优化算法的量子线路,采用COBYLA经典优化算法对参数量子门中的参数进行优化,并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明,使用量子近似优化算法可以在多项式时间内以高概率获得最大独立集问题的解,实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。     

一种改进的量子搜索算法

Rrover提出的对无序数据库进行搜索的量子算法，可以将搜索时间复杂度从经典计算机上的O（N）降低为O（N的平方根）。该算法显示了量子计算的强大能力，在量子计算研究中具有重要地位。但是，我们在研究Grover算法中发现Grover算法存在搜索失效等问题。本文分析了Grover算法中存在的问题，针对其不足之处进行了改进，并证明了改进后量子搜索算法的有效性。     

量子优化算法综述

量子优化是量子计算领域近年来颇受关注的一个研究分支,主要研究如何利用量子计算加速优化问题的求解.根据优化问题的变量是否连续分类梳理量子优化算法,侧重介绍连续变量优化算法.通过对现存工作的调研梳理得到一些观察:1)5～20年前的研究主要集中在离散变量的量子优化技术,近5年的研究则更关注连续变量的量子优化技术;2)量子优化使用的主要基础技术都是10～20年前提出的,在基础技术方面需要进一步革新;3)量子优化算法相比于对应的经典算法通常在理论上有加速优势,既有体现在时间复杂度的加速,也有体现在查询复杂度的加速,但仍然有待更为严格的理论分析;4)优化领域依然存在许多值得量子计算研究人员探索的问题,特别是非凸优化领域,亦即经典计算上认为较难的优化问题.     

基于对称谱的宽带相干信号快速DOA估计

针对聚焦类宽带信号方位估计算法运算量较大的问题,提出了一种快速算法。首先利用矩阵的Toeplitz化重构,不用对阵列进行子阵分割,就可实现宽带信号的解相干;然后根据接收数据协方差矩阵的厄尔米特特性,利用酉变换将复数矩阵映射为实数矩阵,通过在实数域特征分解,降低了特征分解的计算复杂度;最后通过投影子空间正交技术,利用噪声子空间和共轭噪声子空间重新构造空间谱,根据谱对称性,在半谱内搜索即可得到信号的角度,同时使谱峰搜索的运算量降低了一半。理论分析及仿真结果表明,新算法无需聚焦运算,精度较高,运算量小,对宽带相干信号有效。     

一种协方差矩阵的多尺度量子谐振子算法

针对多尺度量子谐振子算法在处理高维全局优化问题时难以收敛的问题,提出一种协方差矩阵的多尺度量子谐振子优化算法,并给出新算法的核心数学模型.所提算法改进了多元正态分布评估算法中的协方差矩阵生成方式,保留了之前采样点的记忆,加入动态迭代步长加快了新协方差矩阵的更新速度.实验结果表明,所提算法的性能远超原算法,与4种经典优化算法相比,在收敛精度、收敛速度和鲁棒性上也具有优势.     

第一寄存器小Qubit量子计算攻击RSA研究

提出了针对RSA的小Qubit量子攻击算法设计,量子攻击的第一量子寄存器所需的Qubit数目由原先至少2L降低到L1,总体空间复杂度记为(L1,L),其中2L1≥r,r为分解所得周期。由于第一寄存器量子比特数的减少,降低了算法复杂度和成功率,且改进原算法中模幂计算,提升运算速率。改进攻击算法的量子电路的时间复杂度为T=O(2L2)。在时间复杂度和空间复杂度上都有明显的进步。改进算法的成功率降低了,但实际成功求解时间,即每次分解时间/成功率,依然低于 Shor 算法目前的主要改进算法。完成了仿真模拟实验,分别用11、10、9 Qubit成功分解119的量子电路。     

随机梯度下降优化的量子多分类支持向量机

为改善大规模数据在经典机器学习多分类任务中的计算负担,本文提出了一种基于随机梯度下降优化的量子多分类支持向量机(SGD-MQSVM)算法。通过采用量子随机梯度下降法获得训练参数,并采用全对多分类支持向量机的量子方法进行多分类。算法的时间复杂性可将单次迭代的时间复杂度从经典多项式级降低到对数级。     

求最优装载的量子算法

随着Grover量子搜索算法的不断发展,它的实际应用价值也在逐渐体现.通过介绍量子并行计算和量子算法的基本思想以及对改进的Grover搜索算法进行研究的基础上,分析给出了一个时间复杂度为O(√N)的求解最优装载问题的量子算法.对于最优装载问题,分别用经典计算机上的贪心算法和量子算法来求解,得出了这两种算法的时间复杂度,从而可以看出量子算法相对于经典算法具有更快的搜索速度.     

一种高效的增量式属性约简算法

针对粗糙集中求属性核和属性约简存在的问题,首先给出了改进的差别矩阵定义,进而提出一种基于改进差别矩阵的核增量式更新算法,用于解决对象动态增加情况下核的更新问题;同时,为了降低现有增量式属性约简算法的时间、空间复杂度,提出一种不存储差别矩阵的高效属性约简算法,用于处理对象动态增加情况下属性约简的更新问题.理论分析及实验结果均表明了所提出算法的有效性和可行性.     

量子线性卷积及其在图像处理中的应用

线性卷积在图像处理中发挥着重要作用,但是在处理海量高分辨率图像时,求解线性卷积会消耗许多计算资源.为此,本文就量子线性卷积及其在图像处理问题中的应用开展相关研究,首先提出单通道,单位步长,零补充情况下的量子一维和二维线性卷积,然后实现多通道,非单位步长,非零补充的情况,最后将量子二维线性卷积应用于量子图像平滑,量子图像锐化和量子图像边缘检测.通过理论分析证明了量子线性卷积的空间复杂度O（logM）和时间复杂度O（log²M）较经典线性卷积有指数级下降,且基于Qiskit的仿真实验成功验证了量子线性卷积和量子图像处理算法的正确性和可行性.