Quantum algorithm for neighborhood preserving embedding
Authors:
- 1 June 2022
- journal article
- research article
- Published by IOP Publishing in Chinese Physics B
- Vol. 31 (6) , 060304
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.Keywords
All Related Versions
This publication has 50 references indexed in Scilit:
- Fixed-Point Quantum Search with an Optimal Number of QueriesPhysical Review Letters, 2014
- Quantum Support Vector Machine for Big Data ClassificationPhysical Review Letters, 2014
- Quantum principal component analysisNature Physics, 2014
- Quantum algorithm and circuit design solving the Poisson equationNew Journal of Physics, 2013
- Quantum Algorithm for Data FittingPhysical Review Letters, 2012
- LOCALLY LINEAR EMBEDDING: A REVIEWInternational Journal of Pattern Recognition and Artificial Intelligence, 2011
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- Quantum networks for elementary arithmetic operationsPhysical Review A, 1996
- RELATIONS BETWEEN TWO SETS OF VARIATESBiometrika, 1936