Quantum algorithm for Neighborhood Preserving Embedding
arXiv:2110.11541 · doi:10.1088/1674-1056/ac523a
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 . However, the algorithm has two disadvantages: (1) It is incomplete in the sense that the input of the third sub-algorithm cannot be obtained by the second sub-algorithm. (2) 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 and an exponential speedup on the dimensionality under certain conditions over the classical NPE algorithm, and achieve significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.
arXiv comment12 pages
References in corpus (33)
- Quantum algorithm for solving linear systems of equations
- Variational Quantum Algorithms
- Quantum support vector machine for big data classification
- Quantum principal component analysis
- Quantum Networks for Elementary Arithmetic Operations
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Quantum algorithms for supervised and unsupervised machine learning
- Quantum Data Fitting
- A Quantum Algorithm for Finding the Minimum
- Prediction by linear regression on a quantum computer
- A quantum-inspired classical algorithm for recommendation systems
- Fixed-point quantum search with an optimal number of queries
- A quantum linear system algorithm for dense matrices
- Quantum algorithm and circuit design solving the Poisson equation
- Quantum Algorithm for Linear Regression
- Quantum machine learning for quantum anomaly detection
- Quantum singular value decomposition of non-sparse low-rank matrices
- Quantum Discriminant Analysis for Dimensionality Reduction and Classification
- Variational Quantum algorithm for Poisson equation
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Quantum data compression by principal component analysis
- Quantum algorithm for association rules mining
- Quantum algorithm for association rules mining
- The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
- Quantum Spectral Clustering
- Quantum Fourier Transform in Computational Basis
- Asymptotic Quantum Algorithm for the Toeplitz Systems
- Quantum algorithm for visual tracking
- Quantum algorithm and quantum circuit for A-Optimal Projection: dimensionality reduction
- Variational Quantum Algorithms for Dimensionality Reduction and Classification
- Improved quantum algorithm for A-optimal projection
- Locally Linear Embedding and its Variants: Tutorial and Survey
- Quantum speedup for twin support vector machines