Quantum algorithm for neighborhood preserving embedding

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...

Full description

Saved in:
Bibliographic Details
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:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1674-1056
DOI:10.1088/1674-1056/ac523a