中国物理B ›› 2022, Vol. 31 ›› Issue (6): 60304-060304.doi: 10.1088/1674-1056/ac523a

• • 上一篇    下一篇

Quantum algorithm for neighborhood preserving embedding

Shi-Jie Pan(潘世杰)1,2, Lin-Chun Wan(万林春)1, Hai-Ling Liu(刘海玲)1, Yu-Sen Wu(吴宇森)1, Su-Juan Qin(秦素娟)1, Qiao-Yan Wen(温巧燕)1, and Fei Gao(高飞)1,†   

  1. 1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China;
    2 State Key Laboratory of Cryptology, P. O. Box 5159, Beijing 100878, China
  • 收稿日期:2021-11-15 修回日期:2022-01-29 接受日期:2022-02-07 出版日期:2022-05-17 发布日期:2022-06-07
  • 通讯作者: Fei Gao E-mail:gaof@bupt.edu.cn
  • 基金资助:
    Project supported by the Fundamental Research Funds for the Central Universities (Grant No. 2019XD-A01) and the National Natural Science Foundation of China (Grant Nos. 61972048 and 61976024).

Quantum algorithm for neighborhood preserving embedding

Shi-Jie Pan(潘世杰)1,2, Lin-Chun Wan(万林春)1, Hai-Ling Liu(刘海玲)1, Yu-Sen Wu(吴宇森)1, Su-Juan Qin(秦素娟)1, Qiao-Yan Wen(温巧燕)1, and Fei Gao(高飞)1,†   

  1. 1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China;
    2 State Key Laboratory of Cryptology, P. O. Box 5159, Beijing 100878, China
  • Received:2021-11-15 Revised:2022-01-29 Accepted:2022-02-07 Online:2022-05-17 Published:2022-06-07
  • Contact: Fei Gao E-mail:gaof@bupt.edu.cn
  • Supported by:
    Project supported by the Fundamental Research Funds for the Central Universities (Grant No. 2019XD-A01) and the National Natural Science Foundation of China (Grant Nos. 61972048 and 61976024).

RichHTML

13

PDF (PC)

431

赞

摘要： Neighborhood preserving embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality n. However, the algorithm has two disadvantages: (i) It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one. (ii) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm, and achieve a significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.

关键词: quantum algorithm, quantum machine learning, amplitude amplification

Abstract: Neighborhood preserving embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality n. However, the algorithm has two disadvantages: (i) It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one. (ii) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm, and achieve a significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.

Key words: quantum algorithm, quantum machine learning, amplitude amplification

中图分类号:  (Quantum algorithms, protocols, and simulations)

  • 03.67.Ac
03.67.Lx (Quantum computation architectures and implementations)