潘世杰,高飞,万林春,秦素娟,温巧燕

¹（网络与交换技术国家重点实验室(北京邮电大学) 北京 100876）；²（密码科学技术国家重点实验室 北京 100878) (panshijie@bupt.edu.cn)

出版日期: 2021-09-01


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

Quantum Algorithm for Spectral Regression

Pan Shijie, Gao Fei, Wan Linchun, Qin Sujuan, Wen Qiaoyan

¹（State Key Laboratory of Networking and Switching Technology (Beijing University of Posts and Telecommunications), Beijing 100876);²(State Key Laboratory of Cryptology, Beijing 100878)

Online: 2021-09-01


Supported by:This work was supported by the Fundamental Research Funds for the Central Universities (2019XD-A01) and the National Natural Science Foundation of China (61976024, 61972048).

摘要/Abstract

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

参考文献

相关文章 1

[1]	张宇鹍, 袁骁. 量子错误缓解研究进展[J]. 计算机研究与发展, 2021, 58(9): 1843-1855.

PDF全文下载地址:

https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4486