Laplacian eigenmap algorithm is a typical nonlinear model for dimensionality reduction in classical machine learning. We propose an efficient quantum Laplacian eigenmap algorithm to exponentially speed up the original counterparts. In our work, we demonstrate that the Hermitian chain product proposed in quantum linear discriminant analysis (arXiv:1510.00113,2015) can be applied to implement quantum Laplacian eigenmap algorithm. While classical Laplacian eigenmap algorithm requires polynomial time to solve the eigenvector problem, our algorithm is able to exponentially speed up nonlinear dimensionality reduction.
Laplacian eigenmap algorithm is a typical nonlinear model for dimensionality reduction in classical machine learning. We propose an efficient quantum Laplacian eigenmap algorithm to exponentially speed up the original counterparts. In our work, we demonstrate that the Hermitian chain product proposed in quantum linear discriminant analysis (arXiv:1510.00113,2015) can be applied to implement quantum Laplacian eigenmap algorithm. While classical Laplacian eigenmap algorithm requires polynomial time to solve the eigenvector problem, our algorithm is able to exponentially speed up nonlinear dimensionality reduction.
We present quantum algorithms to efficiently perform discriminant analysis for dimensionality reduction and classification over an exponentially large input data set. Compared with the best-known classical algorithms, the quantum algorithms show an exponential speedup in both the number of training vectors M and the feature space dimension N . We generalize the previous quantum algorithm for solving systems of linear equations (2009 Phys. Rev. Lett. 103 150502 ) to efficiently implement a Hermitian chain product of k trace-normalized N × N Hermitian positive-semidefinite matrices with time complexity of . Using this result, we perform linear as well as nonlinear Fisher discriminant analysis for dimensionality reduction over M vectors, each in an N -dimensional feature space, in time , where denotes the tolerance error, and p is the number of principal projection directions desired. We also present a quantum discriminant analysis algorithm for data classification with time complexity .
The era of big data has made traditional machine learning algorithms struggle with high-dimensional, nonlinear datasets due to high computational resource consumption, long training times, and limited generalization. Quantum computing, with its exponential parallelism from qubit superposition and entanglement, offers new hope for machine learning. Local Sensitive Discriminant Analysis (LSDA) algorithm is a widely used dimensionality reduction technique in machine learning. However, it is time-consuming when handling large-scale high-dimensional data. This paper proposed a quantum version of LSDA algorithm, which transforms the generalized eigenvalue problem in LSDA into a Hermitian eigenvalue problem, solved using quantum phase estimation and block-encoding techniques. Two post-processing strategies are provided to obtain low-dimensional data for quantum or classical machine learning tasks. The quantum LSDA algorithm obtains polynomial speedups compared to the classical LSDA in terms of the number of data points and dimensionality, showing the potential of quantum technique to boost machine learning efficiency.
With the development of quantum algorithms, high-cost computations are being scrutinized in the hope of a quantum advantage. While graphs offer a convenient framework for multiple real-world problems, their analytics still comes with high computation and space. By mapping the graph data into a low dimensional space, in which graph structural information is preserved, the eigenvectors of the Laplacian matrix constitute a powerful node embedding, called Laplacian Eigenmaps. Computing these embeddings is on its own an expensive task knowing that using specific sparse methods, the eigendecomposition of a Laplacian matrix has a cost of O(rn2), r being the ratio of nonzero elements. We propose a method to compute a Laplacian Eigenmap using a quantum variational circuit. The idea of our algorithm is to reach the eigenstates of the laplacian matrix, which can be considered as a hamiltonian operator, by adapting the variational quantum eigensolver algorithm. By estimating the d first eigenvectors of the Laplacian at the same time, our algorithm directly generates a d dimension quantum embedding of the graph. We demonstrate that it is possible to use the embedding for graph machine learning tasks by implementing a quantum classifier on the top of it. The overall circuit consists in a full quantum node classification algorithm. Tests on 32 nodes graph with a quantum simulator shows that we can achieve similar performances as the classical laplacian eigenmap algorithm. Although mathematical properties of this approximate approach are not fully understood, this algorithm opens perspectives for graph pre-processing using noisy quantum computers.
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). 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.
Abstract Solving eigenproblem of the Laplacian matrix of a fully connected weighted graph has wide applications in data science, machine learning, and image processing, etc. However, this is very challenging because it involves expensive matrix operations. Here, an efficient quantum algorithm is proposed to solve it. Specifically, the optimal Hamiltonian simulation technique based on the block‐encoding framework is adopted to implement the quantum simulation of the Laplacian matrix. Then, the eigenvalues and eigenvectors of the Laplacian matrix are extracted by the quantum phase estimation algorithm. The core of this entire algorithm is to construct a block‐encoding of the Laplacian matrix. To achieve this, how to construct block‐encoding of operators containing the information of the weight matrix and the degree matrix, respectively are shown in detail, and the block‐encoding of the Laplacian matrix is further obtained. Compared with its classical counterpart, this algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex. It is also shown that this algorithm can be extended to solve the eigenproblem of symmetric (non‐symmetric) normalized Laplacian matrix.
As a general framework, Matrix Exponential Dimensionality Reduction (MEDR) deals with the small-sample-size problem that appears in linear Dimensionality Reduction (DR) algorithms. High complexity is the bottleneck in this type of DR algorithm because one has to solve a large-scale matrix exponential eigenproblem. To address it, here we design a general quantum algorithm framework for MEDR based on the block-encoding technique. This framework is configurable, that is, by selecting suitable methods to design the block-encodings of the data matrices, a series of new efficient quantum algorithms can be derived from this framework. Specifically, by constructing the block-encodings of the data matrix exponentials, we solve the eigenproblem and then obtain the digital-encoded quantum state corresponding to the compressed low-dimensional dataset, which can be directly utilized as input state for other quantum machine learning tasks to overcome the curse of dimensionality. As applications, we apply this framework to four linear DR algorithms and design their quantum algorithms, which all achieve a polynomial speedup in the dimension of the sample over their classical counterparts.