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

最大独立集问题是著名的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的量子电路。     

求最优装载的量子算法

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

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

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

量子计算与量子密码的原理及研究进展综述

量子计算与量子密码是基于量子效应的计算技术和密码技术.1984年Bennett和Brassard提出了第一个量子密钥分发协议,开启了量子密码学的研究,此后相继在量子加密、量子签名等领域进行了大量研究.1994年,Shor利用量子Fourier变换,设计了第一个实用的量子算法,在多项式时间内对大整数进行因子分解.1996年,Grover提出了量子搜索算法,能够对无结构数据进行二次加速.Shor算法和Grover算法的提出不仅体现了量子计算的优越性,还对传统基于数学困难问题的密码学体制造成威胁.经过半个世纪的发展,量子计算与量子密码在理论与实践的研究上都取得了丰硕的成果.从量子力学的数学框架、基本概念和原理、量子计算基本思想、量子密码研究进展及主要思想等方面进行总结梳理.     

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

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

Face recognition based on dictionary learning and subspace learning

Dictionary learning plays an important role in sparse representation based face recognition. Many dictionary learning algorithms have been successfully applied to face recognition. However, for corrupted data because of noise or face variations (e.g. occlusion and large pose variation), their performances decline due to the disparity between domains. In this paper, we propose a face recognition algorithm based on dictionary learning and subspace learning (DLSL). In DLSL, a new subspace learning algorithm (SL) is proposed by using sparse constraint, low-rank technology and our label relaxation model to reduce the disparity between domains. Meanwhile, we propose a high-performance dictionary learning algorithm (HPDL) by constructing the embedding term, non-local self-similarity term, and time complexity drop term. In the obtained subspace, we use HPDL to classify these mapped test samples. DLSL is compared with other 28 algorithms on FRGC, LFW, CVL, Yale B and AR face databases. Experimental results show that DLSL achieves better performance than those 28 algorithms, including many state-of-the-art algorithms, such as recurrent regression neural network (RRNN), multimodal deep face recognition (MDFR) and projective low-rank representation (PLR).     

Quantum Algorithms for Learning and Testing Juntas

In this article we develop quantum algorithms for learning and testing juntas, i.e. Boolean functions which depend only on an unknown set of k out of n input variables. Our aim is to develop efficient algorithms: (1) whose sample complexity has no dependence on n, the dimension of the domain the Boolean functions are defined over; (2) with no access to any classical or quantum membership (“black-box”) queries. Instead, our algorithms use only classical examples generated uniformly at random and fixed quantum superpositions of such classical examples; (3) which require only a few quantum examples but possibly many classical random examples (which are considered quite “cheap” relative to quantum examples). Our quantum algorithms are based on a subroutine FS which enables sampling according to the Fourier spectrum of f; the FS subroutine was used in earlier work of Bshouty and Jackson on quantum learning. Our results are as follows: (1) We give an algorithm for testing k-juntas to accuracy ε that uses O(k/ϵ) quantum examples. This improves on the number of examples used by the best known classical algorithm. (2) We establish the following lower bound: any FS-based k-junta testing algorithm requires queries. (3) We give an algorithm for learning k-juntas to accuracy ϵ that uses O(ϵ⁻¹ k log k) quantum examples and O(2 ^k log(1/ϵ)) random examples. We show that this learning algorithm is close to optimal by giving a related lower bound. Supported in part by NSF award CCF-0347282, by NSF award CCF-0523664, and by a Sloan Foundation Fellowship.     

量子机器学习综述

近年来, 机器学习一直是被关注和探讨的研究热点, 被应用到各领域并在其中起着重要作用. 但随着数据量的不断增加, 机器学习算法训练时间越来越长. 与此同时, 量子计算机表现出强大的运算能力. 因此, 有研究人员尝试用量子计算的方法解决机器学习训练时间长的问题, 量子机器学习这一领域应运而生. 量子主成分分析、量子支持向量机、量子深度学习等量子机器学习算法相继被提出, 并有实验证明了量子机器学习算法有显著的加速效果, 使得量子机器学习的研究展现出逐步走高的趋势. 对量子机器学习算法进行综述. 首先介绍量子计算基础; 然后对量子监督学习、量子无监督学习、量子半监督学习、量子强化学习以及量子深度学习5类量子机器学习算法进行介绍; 接着对量子机器学习的相关应用进行介绍并给出了算法实验; 最后进行总结和展望.     

量子机器学习

人工智能和量子物理是上世纪发展起来的两个截然不同但又影响深远的学科.近年来,它们在数据科学方面的结合引起了学术界的高度关注,形成了量子机器学习这个新兴领域.利用量子态的叠加性,量子机器学习有望通过量子并行解决目前机器学习中数据量大,训练过程慢的困难,并有望从量子物理的角度提出新的学习模型.目前该领域的研究还处于探索阶段,涵盖内容虽然广泛,但还缺乏系统的梳理.本文将从数据和算法角度总结量子机器学习与经典机器学习的不同,以及其中涉及的关键加速技巧,针对数据结构(数字型、模拟型),计算技巧(相位估计、Grover搜索、内积计算),基础算法(求解线性系统、主成分分析、梯度算法),学习模型(支持向量机、近邻法、感知器、玻尔兹曼机)等4个方面对现有研究成果进行综述,并建议一些可能的研究方向,供本领域的研究人员参考.     

基于感知学习的垃圾邮件过滤算法

Edelman等人根据其神经元群选择学说（the Theory of Neuronal Group Selection,TNGS）提出了脑感知学习的模型,将该模型中脑对陌生事物的学习类比于垃圾邮件过滤系统中对未知邮件的学习,提出了一种新的基于感知学习的网络垃圾邮件过滤算法,并将其应用于一种基于合作式网络的垃圾邮件过滤系统模型中。系统使用改进的文本数字签名技术得到邮件文本之间的内容相似度矩阵,将其与邮件到达的行为特征等一起作为该算法的参数,最后给出了仿真实验结果。     

公理化模糊共享近邻自适应谱聚类算法

针对传统的谱聚类算法通常利用高斯核函数作为相似性度量,且单纯以距离决定相似性不能充分表现原始数据中固有的模糊性、不确定性和复杂性,导致聚类性能降低的问题。提出了一种公理化模糊共享近邻自适应谱聚类算法,首先结合公理化模糊集理论提出了一种模糊相似性度量方法,利用识别特征来衡量更合适的数据成对相似性,然后采用共享近邻的方法发现密集区域样本点分布的结构和密度信息,并且根据每个点所处领域的稠密程度自动调节参数σ,从而生成更强大的亲和矩阵,进一步提高聚类准确率。实验表明,相较于距离谱聚类、自适应谱聚类、模糊聚类方法和地标点谱聚类,所提算法有着更好的聚类性能。     

量子–经典混合神经网络及其故障诊断应用

量子神经网络由于结合了量子计算和神经网络的优点, 近年来受到了广泛的关注. 然而由于目前量子计算 资源受限(如量子比特数、量子逻辑门的保真度等)以及贫瘠高原现象(量子神经网络优化过程中解空间变得平坦时 出现的训练困难)的存在, 量子神经网络当前还难以大规模训练. 针对上述问题, 本文面向量子–经典混合神经网络 模型提出了一种基于无监督学习的特征提取方法. 所采用的无监督学习方法结合了量子自编码器和K-medoids聚类 方法, 可用于多层次结构的特征学习. 该方法创新地利用了K-mediods方法对训练得到的量子自编码器进行聚类, 以 最大化量子自编码器性质的差异. 进一步, 本文在轴承异常检测问题上, 通过实验验证了所提出的无监督特征提取 方法的有效性和实用性, 测试集准确率在二分类、四分类和十分类分别达到100%, 89.6%和81.6%.     

基于信息粒化的SVM时序回归预测

为了提高SVM的学习效率和泛化能力,首先利用一种信息粒化算法对原始数据进行预处理,该算法能将样本空间划分为多个粒(子空间),降低样本规模,节省时间复杂度.然后将模糊粒化后的信息利用SVM进行回归分析,同时利用交叉验证选出最优的分类器调节参数,可降低分类器的复杂性和提高分类器的泛化能力,避免出现过学习和欠学习.最后通过预测上证指数的实验验证了该算法具有优越的特性,能够较为准确的进行时序回归预测.