Quantum algorithm for neighborhood preserving embedding

• Published in: Chinese physics B 2022-06, Vol.31 (6), p.60304-227
• Main Authors: Pan, Shi-Jie, Wan, Lin-Chun, Liu, Hai-Ling, Wu, Yu-Sen, Qin, Su-Juan, Wen, Qiao-Yan, Gao, Fei
• Format: Article
• Language: English
• Subjects: amplitude amplification; quantum algorithm; quantum machine learning
• ISSN: 1674-1056
• DOI: 10.1088/1674-1056/ac523a

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.