基于量子奇异值估计的岭回归算法

doi:10.3969/j.issn.1007-5461.2024.05.008

量子电子学报 ›› 2024, Vol. 41 ›› Issue (5): 780-792.doi: 10.3969/j.issn.1007-5461.2024.05.008

基于量子奇异值估计的岭回归算法

陈康炯1, 郭躬德2, 林崧2*

(1 福建师范大学光电与信息工程学院, 福建福州 350007; 2 福建师范大学计算机与网络空间安全学院, 福建福州 350007)

收稿日期:2022-09-21 修回日期:2022-10-22 出版日期:2024-09-28 发布日期:2024-09-28
通讯作者: E-mail: lins95@fjnu.edu.cn E-mail: E-mail: lins95@fjnu.edu.cn
作者简介:陈康炯 ( 1996 - ), 广东湛江人, 研究生, 主要从事量子机器学习方面的研究。E-mail: 3466786698@qq.com
基金资助:
国家自然科学基金 (62171131, 61976053, 61772134) , 福建省高等学校新世纪优秀人才支持计划, 福建省自然科学基金 (2022J01186)

Ridge regression algorithm based on quantum singular value estimation

CHEN Kangjiong1 , GUO Gongde2 , LIN Song2*

(1 College of Optoelectronics and Information Engineering, Fujian Normal University, Fuzhou 350007, China; 2 College of Computer and Cyber Security, Fujian Normal University, Fuzhou 350007, China)

Received:2022-09-21 Revised:2022-10-22 Published:2024-09-28 Online:2024-09-28

摘要/Abstract

摘要： 作为一种有监督学习算法, 岭回归算法有着十分广泛的使用。本工作将量子奇异值估计与经典岭回归算法相结合, 提出了一种量子岭回归算法。该算法利用量子计算的并行特性, 实现了对岭回归拟合参数的求解以及预测值的获取。复杂度分析表明, 所提算法有效解决了数据矩阵为非厄米矩阵时需要进行矩阵拓展或者矩阵运算的问题, 与经典算法相比在运行时间上具有指数级加速。此外, 本工作还给出了所提算法的量子电路图并对其关键步骤进行了仿真实验, 实验结果验证了所提算法的有效性和可行性。

关键词: 量子计算, 量子岭回归, 量子奇异值估计, 量子幅度估计

Abstract: As a kind of supervised learning algorithm, ridge regression algorithm has a wide range of applications. A quantum ridge regression algorithm is proposed by combining quantum singular value estimation with classical ridge regression algorithm. In the proposed algorithm, the parallel property of quantum computation is utilized to solve the fitting parameters of ridge regression and obtain the predicted values. Complexity analysis shows that the proposed algorithm effectively solves the problem of matrix expansion or matrix operation when the data matrix is non-Hermitian matrix, and has exponential acceleration in running time compared with the classical algorithms. In addition, the quantum circuit diagram of the proposed algorithm is also provided and the key steps of the algorithm are simulated. The simulation results confirm its effectiveness and feasibility.

Key words: quantum computing, quantum ridge regression, quantum singular value estimation, quantum amplitude estimation

中图分类号:

TP319

陈康炯, 郭躬德, 林崧. 基于量子奇异值估计的岭回归算法[J]. 量子电子学报, 2024, 41(5): 780-792.

CHEN Kangjiong , GUO Gongde , LIN Song. Ridge regression algorithm based on quantum singular value estimation[J]. Chinese Journal of Quantum Electronics, 2024, 41(5): 780-792.

参考文献

[1]Hilbert M, López P.The world’s technological capacity to store,communicate,and compute information[J].Science, 2011, 332(6025):60-65 [2]Feynman R P.Simulating physics with computers [M]. CRC Press, 2018, 133-153. [3]Montanaro A.Quantum algorithms: an overviewnpj Quantum Information. 2016,2(1): 1-8.[J].npj Quantum Information, 2016, 2(1):1-8 [4]Rebentrost P, Mohseni M, Lloyd S.Quantum support vector machine for big data classification[J].Physical Review Letters, 2014, 113(13):1-5 [5]Schuld M, Fingerhuth M, Petruccione F.Implementing a distance-based classifier with a quantum interference circuit[J].Europhysics Letters, 2017, 119(6):1-7 [6]Wiebe N, Kapoor A, Svore K M.Quantum nearest-neighbor algorithms for machine learning[J].Quantum Information & Computation, 2015, 15(3-4):318-358 [7]Pudenz K L, Lidar D A.Quantum adiabatic machine learning[J].Quantum Information Processing, 2013, 12(5):2027-2070 [8]Lu C Y, Guo G D, Lin S.Bayesian Binary Classification Algorithm Based on Quantum Counting[J].Journal of Nanjing normal University, 2021, 44(04):117-121 [9]陆春悦, 郭躬德, 林崧.基于量子计数的贝叶斯二元分类算法[J].南京师大学报自然科学版, 2021, 44(04):117-121 [10]Xu Y Z, Guo G D, Cai B B, et al.Quantum clustering algorithm based on one-dimensional three-state quantum walk[J].Computer Science, 2016, 43(3):80-83 [11]徐永振, 郭躬德, 蔡彬彬, 等.基于一维三态量子游走的量子聚类算法[J].计算机科学, 2016, 43(3):80-83 [12]Llet R, Ortiz M C, Sarabia L A, et al.Selecting variables for k-means cluster analysis by using a genetic algorithm that optimises the silhouettes[J].Analytica Chimica Acta, 2004, 515(1):87-100 [13]Lloyd S, Mohseni M, Rebentrost P.Quantum principal component analysis[J].Nature Physics, 2014, 10(9):631-633 [14]Yu C H, Gao F, Lin S, et al.Quantum data compression by principal component analysis[J].Quantum Information Processing, 2019, 18(8):1-20 [15]Cong I, Duan L.Quantum discriminant analysis for dimensionality reduction and classification[J].New Journal of Physics, 2016, 18(7):1-10 [16]Chen S L, Huang C H.Construction of continuous-variable coherent state quantum neural network model[J].Chinese Journal of Quantum Electronics, 2017, 34(4):467-472 [17]陈珊琳, 黄春晖.连续变量相干态量子神经网络模型的构建[J].量子电子学报, 2017, 34(4):467-472 [18]Cong I, Choi S, Lukin M D.Quantum convolutional neural networks[J].Nature Physics, 2019, 15(12):1273-1278 [19]Rebentrost P, Bromley T R, Weedbrook C, et al.Quantum Hopfield neural network[J].Physical Review A, 2018, 98(4):1-11 [20]Zhao Z, Pozas-Kerstjens A, Rebentrost P, et al.Bayesian deep learning on a quantum computer[J].Quantum Machine Intelligence, 2019, 1(1):41-51 [21]Harrow A W, Hassidim A, Lloyd S.Quantum algorithm for linear systems of equations[J].Physical Review Letters, 2009, 103(15):1-4 [22]Wiebe N, Braun D, Lloyd S.Quantum algorithm for data fitting[J].Physical Review Letters, 2012, 109(5):1-5 [23]Schuld M, Sinayskiy I, Petruccione F.Prediction by linear regression on a quantum computer[J].Physical Review A, 2016, 94(2):1-5 [24]Liu Y, Zhang S.Fast quantum algorithms for least squares regression and statistic leverage scores[J].Theoretical Computer Science, 2017, 657(2):38-47 [25]Yu C H, Gao F, Wen Q Y.An improved quantum algorithm for ridge regression[J].IEEE Transactions on Knowledge and Data Engineering, 2019, 33(3):858-866 [26]Chen M H, Yu C H, Guo G D, et al.Faster quantum ridge regression algorithm for prediction[J].International Journal of Machine Learning and Cybernetics, 2022, 13(4):1-8 [27]Hoerl A E, Kennard R W.Ridge regression: Biased estimation for nonorthogonal problems[J].Technometrics, 1970, 12(1):55-67 [28]Giovannetti V, Lloyd S, Maccone L.Quantum random access memory[J].Physical Review Letters, 2008, 100(16):1-4 [29]Kaneko K, Miyamoto K, Takeda N, et al.Linear regression by quantum amplitude estimation and its extension to convex optimization[J].Physical Review A, 2021, 104(2):1-12 [30]Mu?oz-Coreas E, Thapliyal H.Quantum circuit design of a t-count optimized integer multiplier[J].IEEE Transactions on Computers, 2018, 68(5):729-739 [31]Kerenidis I, Prakash A.Quantum recommendation systems[J].arXiv, 2016, 1603(03):08675-08675 [32]Wossnig L, Zhao Z, Prakash A.Quantum linear system algorithm for dense matrices[J].Physical Review Letters, 2018, 120(5):1-5 [33]Brassard G, Hoyer P, Mosca M, et al.Quantum amplitude amplification and estimation[J].Contemporary Mathematics, 2002, 305(4):53-74 [34]Chen S, Liu Y, Lyu M R, et al.Fast Relative-Error Approximation Algorithm for Ridge Regression[C]//Uncertainty in Artificial Intelligence. AUAI Press, 2015: 201-210.

基于量子奇异值估计的岭回归算法

Ridge regression algorithm based on quantum singular value estimation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	吴限, 冯世光, 李绿周. 可逆电路综合与优化的若干研究进展[J]. 量子电子学报, 2024, 41(4): 565-577.
[2]	曹可欣, 陈新宇, 朱明强, 李响, 程学云, 管致锦. 基于动态前瞻深度的量子线路映射研究[J]. 量子电子学报, 2024, 41(4): 626-637.
[3]	陈新宇 , 曹可欣 , 朱明强 , 程学云 , 冯世光 , 管致锦. 一种分布式量子计算中传输代价的优化方法[J]. 量子电子学报, 2024, 41(2): 318-329.
[4]	李响 , 姜一博 , 曹可欣 , 朱明强 , 程学云 , 朱鹏程 , 管致锦. 基于SVM的量子线路输出校准方法研究[J]. 量子电子学报, 2024, 41(2): 357-366.
[5]	杨辉 , 李志强 , 潘文杰 , 杨冬晗 , 吴希. 量子近似优化算法在数字分区问题中的应用[J]. 量子电子学报, 2024, 41(2): 367-377.
[6]	王升斌, 窦猛汉, 吴玉椿, 郭国平, 郭光灿 . 分布式量子计算研究进展[J]. 量子电子学报, 2024, 41(1): 1-25.
[7]	卫丽华 , 朱鹏程 , 管致锦 . 基于随机优化模型的量子线路映射辅助设计方法[J]. 量子电子学报, 2023, 40(6): 952-962.
[8]	季雯 , 叶宾 , . HHL 量子算法的普适量子线路设计[J]. 量子电子学报, 2023, 40(5): 747-758.
[9]	朱明强, 申文杰, 牛义仁, 张超, 程学云, 管致锦, 陈亮. 面向可靠性的CNOT量子线路最近邻综合[J]. 量子电子学报, 2023, 40(4): 560-569.
[10]	李志强胡佳佳张威潘苏含戴娟杨冬晗吴希. 求解量子逻辑电路酉矩阵的快速方法[J]. 量子电子学报, 2020, 37(2): 222-228.
[11]	沈鸣燕1，程学云1,2，管致锦1*,陈加庆1，何娴雅1. 一种量子线路二维近邻实现方法[J]. 量子电子学报, 2019, 36(4): 476-482.
[12]	杨春蕾普杰信董永生刘中华梁灵飞. 一种基于量子机制的图像显著性检测方案[J]. J4, 2017, 34(3): 305-315.
[13]	陈月月, 刘呈普, 冯勋立. 克服腔QED中比特反转错误的无退相干子空间量子计算[J]. J4, 2016, 33(5): 553-560.
[14]	王新良杨茜惠靳翔. 基于量子计算的僵尸网络周期性通信行为检测算法[J]. J4, 2016, 33(2): 182-187.
[15]	王乐刘莹王岩岩赵生妹. 基于重叠法的(49,1,9)量子码CNOT门扩展矩形容错构造[J]. J4, 2014, 31(2): 179-185.