Isometric feature mapping (Isomap) is a nonlinear dimensionality reduction algorithm based on the concept of manifold learning. The algorithm is widely used in neuroimaging, spectral analysis, and other fields. While Isomap performs well in certain scenarios, it still faces the challenge of time complexity when dealing with large-scale data sets. In this paper, we proposed a quantum Isomap algorithm that runs with quadratic dependence on the number of data points. Technically, our algorithm is based on two subroutines, quantum Floyd's algorithm and quantum multidimensional scaling. They are of independent interest and may serve as potential tools for addressing other problems.
Isometric feature mapping (Isomap) is a nonlinear dimensionality reduction algorithm based on the concept of manifold learning. The algorithm is widely used in neuroimaging, spectral analysis, and other fields. While Isomap performs well in certain scenarios, it still faces the challenge of time complexity when dealing with large-scale data sets. In this paper, we proposed a quantum Isomap algorithm that runs with quadratic dependence on the number of data points. Technically, our algorithm is based on two subroutines, quantum Floyd's algorithm and quantum multidimensional scaling. They are of independent interest and may serve as potential tools for addressing other problems.
Isomap algorithm is a representative manifold learning algorithm. The algorithm simplifies the data analysis process and is widely used in neuroimaging, spectral analysis and other fields. However, the classic Isomap algorithm becomes unwieldy when dealing with large data sets. Our object is to accelerate the classical algorithm with quantum computing, and propose the quantum Isomap algorithm. The algorithm consists of two sub-algorithms. The first one is the quantum Floyd algorithm, which calculates the shortest distance for any two nodes. The other is quantum Isomap algorithm based on quantum Floyd algorithm, which finds a low-dimensional representation for the original high-dimensional data. Finally, we analyze that the quantum Floyd algorithm achieves exponential speedup without sampling. In addition, the time complexity of quantum Isomap algorithm is O(dNpolylogN). Both algorithms reduce the time complexity of classical algorithms.
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.
Inspired by random walks on graphs, the diffusion map (DM) is a class of unsupervised machine learning that offers automatic identification of low-dimensional data structure hidden in a high-dimensional data set. In recent years, among its many applications, the DM has been successfully applied to discover relevant order parameters in many-body systems, enabling automatic classification of quantum phases of matter. However, a classical DM algorithm is computationally prohibitive for a large data set, and any reduction of the time complexity would be desirable. With a quantum computational speedup in mind, we propose a quantum algorithm for the DM, termed the quantum diffusion map (qDM). Our qDM takes as an input N classical data vectors, performs an eigendecomposition of the Markov transition matrix in time O(log3N), and classically constructs the diffusion map via the readout (tomography) of the eigenvectors, giving a total expected runtime proportional to N2polylogN. Finally, quantum subroutines in the qDM for constructing a Markov transition matrix and for analyzing its spectral properties can also be useful for other random-walk-based algorithms.
Abstract Kernel principal component analysis (kernel PCA) is a nonlinear dimensionality reduction technique that employs kernel functions to map data into a high-dimensional feature space, thereby extending the applicability of linear PCA to nonlinear data and facilitating the extraction of informative principal components. However, kernel PCA necessitates the manipulation of large-scale matrices, leading to high computational complexity and posing challenges for efficient implementation in big data environments. Quantum computing has recently been integrated with kernel methods in machine learning, enabling effective analysis of input data within intractable feature spaces. Although existing quantum kernel PCA proposals promise exponential speedups, they impose stringent requirements on quantum hardware that are challenging to fulfill. In this work, we propose a quantum algorithm for kernel PCA by establishing a connection between quantum kernel methods and block encoding, thereby diagonalizing the centralized kernel matrix on a quantum computer. The query complexity is logarithmic with respect to the size of the data vector, D , and linear with respect to the size of the dataset. An exponential speedup could be achieved when the dataset consists of a few high-dimensional vectors, wherein the dataset size is polynomial in log ( D ) , with D being significantly large. In contrast to existing work, our algorithm enhances the efficiency of quantum kernel PCA and reduces the requirements for quantum hardware. Furthermore, we have also demonstrated that the algorithm based on block encoding matches the lower bound of query complexity, indicating that our algorithm is nearly optimal. Our research has laid down new pathways for developing quantum machine learning algorithms aimed at addressing tangible real-world problems and demonstrating quantum advantages within machine learning.
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.
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.