Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum locally linear embedding

Xi He, Sun Li, Chufan Lyu, Xiaoting Wang

Published Oct 17, 2019• 2 citations
OpenAlex

Abstract

Reducing the dimension of nonlinear data is crucial in data processing and visualization. The locally linear embedding algorithm (LLE) is specifically a representative nonlinear dimensionality reduction method with well maintaining the original manifold structure. In this paper, we present two implementations of the quantum locally linear embedding algorithm (qLLE) to perform the nonlinear dimensionality reduction on quantum devices. One implementation, the linear-algebra-based qLLE algorithm utilizes quantum linear algebra subroutines to reduce the dimension of the given data. The other implementation, the variational qLLE algorithm utilizes a variational quantum-classical hybrid procedure to acquire the low-dimensional data. The classical LLE algorithm requires polynomial time complexity of $N$, where $N$ is the global number of the original high-dimensional data. In data preprocessing, we invoke the quantum $k$-nearest neighbors algorithm ($k$-NN) to find out the $k$ nearest neighbors of the given data with quadratic speedup. For the main part of the qLLE algorithm, compared with the corresponding classical algorithm, the linear-algebra-based qLLE algorithm proposed in this paper achieves an exponential speedup in $O(\mathrm{poly}(\log N))$. The variational qLLE algorithm can be implemented on the near term quantum devices. In addition, the corresponding quantum circuits of the qLLE algorithm are also presented.

Related papers

Quantum algorithm for neighborhood preserving embedding

Shi‐Jie Pan, Lin‐Chun Wan, Hailing Liu +4 more

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.

arXiv:2110.11541•Chinese Physics B•Feb 7, 2022•25 citations

Variational Quantum Isometric Feature Mapping

Guoqing Gong

Currently, big data often encounters "curse of dimensionality" problems. Using classic nonlinear dimensionality reduction algorithm, the complexity increases sharply with the increase of data dimension and quantity. While, quantum dimensionality reduction algorithm can achieve exponential acceleration for large-scale data processing, it requires a large number of n -qubit operations. To solve the problems above, this paper proposed a variational quantum isometric feature mapping algorithm based on classical nonlinear dimensionality reduction algorithm, quantum machine learning algorithm and variational quantum algorithm. In the data processing stage, the quantum k-nearest neighbor algorithm is used to obtain the K nearest neighbors of the original data, construct the adjacency graph, and calculate the geodesic distance between each point to get the distance matrix. The inner product matrix is obtained by redesigning the quantum circuit. Then the characteristic problem of the inner product matrix is solved by using the variational quantum eigensolver. Finally, the representation of low-dimensional data after dimensionality reduction is obtained, and the nonlinear dimensionality reduction of large-scale high-dimensional data is realized.

International Symposium on Computer Technology and Information Science (ISCTIS)•Jul 12, 2024•1 citation

Quantum algorithm for the nonlinear dimensionality reduction with arbitrary kernel

Yaochong Li, Ri‐Gui Zhou, Ruiqing Xu +2 more

Abstract Dimensionality reduction (DR) techniques play an extremely critical role in the data mining and pattern recognition field. However, most DR approaches involve large-scale matrix computations, which cause too high running complexity to implement in the big data scenario efficiently. The recent developments in quantum information processing provide a novel path to alleviate this problem, where a potential quantum acceleration can be obtained comparing with the classical counterpart. Nevertheless, existing proposals for quantum DR methods faced the common dilemma of the nonlinear generalization owing to the intrinsic linear limitation of quantum computation. In this paper, an architecture to simulate the arbitrary nonlinear kernels on a universal quantum computer is illustrated and further propose the quantum kernel principal component analysis (QKPCA) algorithm. The key idea is employing the truncated Taylor expansion to approximate the arbitrary nonlinear kernel within the fixed error and then constructing the corresponding Hamiltonian simulation for the quantum phase estimation algorithm. It is demonstrated theoretically that the QKPCA is qualified for the nonlinear DR task while the exponential speedup is also maintained. In addition, this research has the potential ability to develop other quantum DR approaches and existing linear quantum machine learning models.

Quantum Science and Technology•Oct 5, 2020•36 citations

Variational quantum algorithms for dimensionality reduction and classification

Jin‐Min Liang, Shu‐Qian Shen, Ming Li +1 more

In this work, we present a quantum neighborhood preserving embedding and a quantum local discriminant embedding for dimensionality reduction and classification. We demonstrate that these two algorithms have an exponential speedup over their respectively classical counterparts. Along the way, we propose a variational quantum generalized eigenvalue solver that finds the generalized eigenvalues and eigenstates of a matrix pencil $(\mathcal{G},\mathcal{S})$. As a proof of principle, we implement our algorithm to solve ${2}^{5}\ifmmode\times\else\texttimes\fi{}{2}^{5}$ generalized eigenvalue problems. Finally, our results offer two optional outputs with quantum or classical form, which can be directly applied in another quantum or classical machine learning process.

arXiv:1910.12164•Physical Review A•Mar 16, 2020•41 citations

Quantum algorithm for random-walk-assisted nonlinear dimensionality reduction

Apimuk Sornsaeng, Thiparat Chotibut, Ninnat Dangniam

Dimensionality reduction is an unsupervised learning technique that uncovers the underlying low-dimensional structure in highdimensional data sets. Random walks on graphs for dimensionality reduction, such as diffusion maps (DM) and the Potential of Heat-diffusion for Affinity-based Trajectory Embedding (PHATE), have emerged as powerful tools for automatically identifying low-dimensional data. These methods have applications in various fields, including many-body physics and bioinformatics. However, the classical implementations of DM and PHATE suffer from a computational bottleneck caused by the eigendecomposition step, which has a cubic time complexity to the size of the data set, rendering them impractical for large data sets. Leveraging the quantum computational speedup, we propose a quantum analog of nonlinear dimensionality reduction, named the quantum diffusion map (qDM), which can significantly reduce the computational cost of constructing the Markov transition matrix. Specifically, our algorithm can construct the Markov transition matrix for N classical data vectors in O(log3 N) time and extract the eigenpairs of the transition matrix classically to construct the DM with an expected runtime of N2polylogN. Moreover, the quantum subroutines utilized in our algorithm have potential applications beyond dimensionality reduction, for example, in any random-walk-based problems requiring Markov transition matrix construction and spectral analysis.

•Jan 1, 2022•0 citations

基于最大方差展开的量子非线性降维

ZHANG Xin, Gongde Guo, YU ChaoHua +1 more

Maximum variance unfolding is a nonlinear dimensionality reduction algorithm based on the local equidistance of manifolds. However, it is quite computationally expensive, especially when dealing with large-scale datasets. Therefore, an efficient quantum maximum variance unfolding algorithm is proposed herein. First, we propose a quantum matrix square root algorithm with exponential speedup, which can be used to obtain the square root of the involved matrix. As a result, we can efficiently obtain the density operator of the Laplacian matrix. Then, a complete quantum dimensionality reduction algorithm is proposed to map the original high-dimensional data onto a low-dimensional data space using Hamiltonian simulation and phase estimation. Finally, our research reveals that compared with its classical counterpart, the proposed quantum dimensionality reduction algorithm achieves an exponential speedup in terms of dimension and a polynomial speedup in terms of number of samples.

Zhongguo kexue. Wulixue Lixue Tianwenxue•Mar 1, 2024•1 citation
Reducing the dimension of nonlinear data is crucial in data processing and visualization. The locally linear embedding algorithm (LLE) is specifically a representative nonlinear dimensionality reduction method with well maintaining the original manifold structure. In this paper, we present two implementations of the quantum locally linear embedding algorithm (qLLE) to perform the nonlinear dimensionality reduction on quantum devices. One implementation, the linear-algebra-based qLLE algorithm utilizes quantum linear algebra subroutines to reduce the dimension of the given data. The other implementation, the variational qLLE algorithm utilizes a variational quantum-classical hybrid procedure to acquire the low-dimensional data. The classical LLE algorithm requires polynomial time complexity of NNN, where NNN is the global number of the original high-dimensional data. In data preprocessing, we invoke the quantum kkk-nearest neighbors algorithm (kkk-NN) to find out the kkk nearest neighbors of the given data with quadratic speedup. For the main part of the qLLE algorithm, compared with the corresponding classical algorithm, the linear-algebra-based qLLE algorithm proposed in this paper achieves an exponential speedup in O(poly(log⁡N))O(\mathrm{poly}(\log N))O(poly(logN)). The variational qLLE algorithm can be implemented on the near term quantum devices. In addition, the corresponding quantum circuits of the qLLE algorithm are also presented.
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.
Currently, big data often encounters "curse of dimensionality" problems. Using classic nonlinear dimensionality reduction algorithm, the complexity increases sharply with the increase of data dimension and quantity. While, quantum dimensionality reduction algorithm can achieve exponential acceleration for large-scale data processing, it requires a large number of n -qubit operations. To solve the problems above, this paper proposed a variational quantum isometric feature mapping algorithm based on classical nonlinear dimensionality reduction algorithm, quantum machine learning algorithm and variational quantum algorithm. In the data processing stage, the quantum k-nearest neighbor algorithm is used to obtain the K nearest neighbors of the original data, construct the adjacency graph, and calculate the geodesic distance between each point to get the distance matrix. The inner product matrix is obtained by redesigning the quantum circuit. Then the characteristic problem of the inner product matrix is solved by using the variational quantum eigensolver. Finally, the representation of low-dimensional data after dimensionality reduction is obtained, and the nonlinear dimensionality reduction of large-scale high-dimensional data is realized.
Abstract Dimensionality reduction (DR) techniques play an extremely critical role in the data mining and pattern recognition field. However, most DR approaches involve large-scale matrix computations, which cause too high running complexity to implement in the big data scenario efficiently. The recent developments in quantum information processing provide a novel path to alleviate this problem, where a potential quantum acceleration can be obtained comparing with the classical counterpart. Nevertheless, existing proposals for quantum DR methods faced the common dilemma of the nonlinear generalization owing to the intrinsic linear limitation of quantum computation. In this paper, an architecture to simulate the arbitrary nonlinear kernels on a universal quantum computer is illustrated and further propose the quantum kernel principal component analysis (QKPCA) algorithm. The key idea is employing the truncated Taylor expansion to approximate the arbitrary nonlinear kernel within the fixed error and then constructing the corresponding Hamiltonian simulation for the quantum phase estimation algorithm. It is demonstrated theoretically that the QKPCA is qualified for the nonlinear DR task while the exponential speedup is also maintained. In addition, this research has the potential ability to develop other quantum DR approaches and existing linear quantum machine learning models.
In this work, we present a quantum neighborhood preserving embedding and a quantum local discriminant embedding for dimensionality reduction and classification. We demonstrate that these two algorithms have an exponential speedup over their respectively classical counterparts. Along the way, we propose a variational quantum generalized eigenvalue solver that finds the generalized eigenvalues and eigenstates of a matrix pencil (G,S)(\mathcal{G},\mathcal{S})(G,S). As a proof of principle, we implement our algorithm to solve ${2}^{5}\ifmmode\times\else\texttimes\fi{}{2}^{5}$ generalized eigenvalue problems. Finally, our results offer two optional outputs with quantum or classical form, which can be directly applied in another quantum or classical machine learning process.
Dimensionality reduction is an unsupervised learning technique that uncovers the underlying low-dimensional structure in highdimensional data sets. Random walks on graphs for dimensionality reduction, such as diffusion maps (DM) and the Potential of Heat-diffusion for Affinity-based Trajectory Embedding (PHATE), have emerged as powerful tools for automatically identifying low-dimensional data. These methods have applications in various fields, including many-body physics and bioinformatics. However, the classical implementations of DM and PHATE suffer from a computational bottleneck caused by the eigendecomposition step, which has a cubic time complexity to the size of the data set, rendering them impractical for large data sets. Leveraging the quantum computational speedup, we propose a quantum analog of nonlinear dimensionality reduction, named the quantum diffusion map (qDM), which can significantly reduce the computational cost of constructing the Markov transition matrix. Specifically, our algorithm can construct the Markov transition matrix for N classical data vectors in O(log3 N) time and extract the eigenpairs of the transition matrix classically to construct the DM with an expected runtime of N2polylogN. Moreover, the quantum subroutines utilized in our algorithm have potential applications beyond dimensionality reduction, for example, in any random-walk-based problems requiring Markov transition matrix construction and spectral analysis.
Maximum variance unfolding is a nonlinear dimensionality reduction algorithm based on the local equidistance of manifolds. However, it is quite computationally expensive, especially when dealing with large-scale datasets. Therefore, an efficient quantum maximum variance unfolding algorithm is proposed herein. First, we propose a quantum matrix square root algorithm with exponential speedup, which can be used to obtain the square root of the involved matrix. As a result, we can efficiently obtain the density operator of the Laplacian matrix. Then, a complete quantum dimensionality reduction algorithm is proposed to map the original high-dimensional data onto a low-dimensional data space using Hamiltonian simulation and phase estimation. Finally, our research reveals that compared with its classical counterpart, the proposed quantum dimensionality reduction algorithm achieves an exponential speedup in terms of dimension and a polynomial speedup in terms of number of samples.