量子谱回归算法

作     者：潘世杰 高飞 万林春 秦素娟 温巧燕 Pan Shijie;Gao Fei;Wan Linchun;Qin Sujuan;Wen Qiaoyan

作者机构：网络与交换技术国家重点实验室(北京邮电大学)北京100876 密码科学技术国家重点实验室北京100878 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2021年第58卷第9期

页      面：1835-1842页

核心收录：

学科分类：07[理学] 070201[理学-理论物理] 0702[理学-物理学] 

基　　金：中央高校基本科研业务费专项资金(2019XD-A01) 国家自然科学基金项目(61976024,61972048) 

主　　题：量子算法 量子机器学习 谱回归 子空间学习 稠密矩阵 

摘      要：子空间学习是机器学习领域的重要研究方向.为了降低子空间学习的复杂度,Cai等人提出了谱回归降维框架,并针对结合标签构造对应图的子空间学习提出了高效谱回归.近年来,量子计算的发展使进一步降低子空间学习算法的复杂度成为了可能.Meng等人率先提出了量子谱回归算法(MYXZ算法).MYXZ算法用了稀疏哈密顿量模拟技术来处理由权重矩阵生成的矩阵,但这个矩阵在较多的情况下是稠密矩阵.针对这种情况,指出了MYXZ算法的局限性,提出了一个改进的量子谱回归算法.改进算法采用了量子奇异值估计技术,在处理稠密矩阵时相对MYXZ算法有多项式加速.另外,提出了一个新的量子算法,对经典的高效谱回归进行加速.新算法能处理的这类问题是MYXZ算法无法处理的.新算法利用了量子岭回归和量子矩阵向量乘技术,在相同的参数条件下相对经典算法具有多项式加速效果.