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...
Saved in:
Published in: | Chinese physics B 2022-06, Vol.31 (6), p.60304-227 |
---|---|
Main Authors: | , , , , , , |
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!
|
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 |