• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Pan Shijie, Gao Fei, Wan Linchun, Qin Sujuan, Wen Qiaoyan. Quantum Algorithm for Spectral Regression[J]. Journal of Computer Research and Development, 2021, 58(9): 1835-1842. DOI: 10.7544/issn1000-1239.2021.20210366
Citation: Pan Shijie, Gao Fei, Wan Linchun, Qin Sujuan, Wen Qiaoyan. Quantum Algorithm for Spectral Regression[J]. Journal of Computer Research and Development, 2021, 58(9): 1835-1842. DOI: 10.7544/issn1000-1239.2021.20210366

Quantum Algorithm for Spectral Regression

Funds: 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).
More Information
  • Published Date: August 31, 2021
  • Subspace learning is an important research direction in the field of machine learning. In order to reduce the complexity of subspace learning, Cai et al. proposed a spectral regression dimensionality reduction framework, and proposed efficient spectral regression for subspace learning that constructed their graph by incorporating the label information. In recent years, the development of quantum computing has made it possible to further reduce the complexity of subspace learning algorithms. Meng et al. pioneered the quantum algorithm for spectral regression (MYXZ algorithm). In this article, the limitations of the MYXZ algorithm are pointed out. We point out that MYXZ algorithm uses sparse Hamiltonian simulation technology to process the matrix generated by the weight matrix, but this matrix is a dense matrix in some cases. In response to this situation, we propose an improved quantum spectral regression algorithm. Our improved algorithm uses quantum singular value estimation technology, which has a polynomial acceleration compared with MYXZ algorithm when dealing with dense matrices. In addition, we propose a new quantum algorithm to accelerate the classical efficient spectral regression. The problems that our new algorithm can handle cannot be handled by MYXZ algorithm. Our algorithm utilizes quantum ridge regression and quantum matrix vector multiplication technology. Under the same parameter conditions, our algorithm has polynomial acceleration effect compared with the classical algorithm.
  • Related Articles

    [1]Fu Liguo, Pang Jianmin, Wang Jun, Zhang Jiahao, Yue Feng. Formal Model of Correctness and Optimization on Binary Translation[J]. Journal of Computer Research and Development, 2019, 56(9): 2001-2011. DOI: 10.7544/issn1000-1239.2019.20180513
    [2]Zhou Zhibin, Wang Guojun, Liu Qin, Jia Weijia. A RFID Anonymous Grouping Proof Protocol Using Dual-Layer Verification[J]. Journal of Computer Research and Development, 2018, 55(12): 2674-2684. DOI: 10.7544/issn1000-1239.2018.20170787
    [3]Fu Yanyan, Zhang Min, Chen Kaiqu, Feng Dengguo. Proofs of Data Possession of Multiple Copies[J]. Journal of Computer Research and Development, 2014, 51(7): 1410-1416.
    [4]Li Tao, Zhang Jingzhong. Machine Proofs in Geometry Based on Complex Number Method[J]. Journal of Computer Research and Development, 2013, 50(9): 1963-1969.
    [5]Ma Yanfang, Zhang Min, Chen Yixiang. Formal Description of Software Dynamic Correctness[J]. Journal of Computer Research and Development, 2013, 50(3): 626-635.
    [6]Wang Yong, Fang Juan, Ren Xingtian, and Lin Li. Formal Verification of TCG Remote Attestation Protocols Based on Process Algebra[J]. Journal of Computer Research and Development, 2013, 50(2): 325-331.
    [7]Wang Changjing. Verifying the Correctness of Loop Optimization Based on Extended Logic Transformation System μTS[J]. Journal of Computer Research and Development, 2012, 49(9): 1863-1873.
    [8]Jing Shuxu, He Fazhi, Cai Xiantao, Cheng Yuan. A Method for Object Reference in Collaborative Modeling System[J]. Journal of Computer Research and Development, 2011, 48(11): 2031-2038.
    [9]Si Tiange, Tan Zhiyong, and Dai Yiqi. A Security Proof Method for Multilevel Security Models[J]. Journal of Computer Research and Development, 2008, 45(10): 1711-1717.
    [10]Wang Guilin, Qing Sihan. Security Notes on Two Cheat-Proof Secret Sharing Schemes[J]. Journal of Computer Research and Development, 2005, 42(11): 1924-1927.

Catalog

    Article views (619) PDF downloads (249) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return