In this paper, we propose an efficient quantum algorithm for spectral regression which is a dimensionality reduction framework based on the regression and spectral graph analysis. The quantum algorithm involves two core subroutines: the quantum principal eigenvectors analysis and the quantum ridge regression algorithm. The quantum principal eigenvectors analysis can be performed by an efficient sparse Hamiltonian simulation. For the ridge regression, we propose a quantum algorithm that is derived from the quantum singular value decomposition method. Our quantum ridge regression algorithm is more suitable for data matrices that are non-sparse and skewed. Our analysis demonstrates that the quantum subroutines can be implemented with an approximatively polynomial speedup on a quantum computer over their classical counterparts.
In this paper, we propose an efficient quantum algorithm for spectral regression which is a dimensionality reduction framework based on the regression and spectral graph analysis. The quantum algorithm involves two core subroutines: the quantum principal eigenvectors analysis and the quantum ridge regression algorithm. The quantum principal eigenvectors analysis can be performed by an efficient sparse Hamiltonian simulation. For the ridge regression, we propose a quantum algorithm that is derived from the quantum singular value decomposition method. Our quantum ridge regression algorithm is more suitable for data matrices that are non-sparse and skewed. Our analysis demonstrates that the quantum subroutines can be implemented with an approximatively polynomial speedup on a quantum computer over their classical counterparts.
Ridge regression (RR) is an important machine learning technique which introduces a regularization hyperparameterαto ordinary multiple linear regression for analyzing data suffering from multicollinearity. In this paper, we present a quantum algorithm for RR, where the technique of parallel Hamiltonian simulation to simulate a number of Hermitian matrices in parallel is proposed and used to develop a quantum version ofK-fold cross-validation approach, which can efficiently estimate the predictive performance of RR. Our algorithm consists of two phases: (1) using quantumK-fold cross-validation to efficiently determine a goodαwith which RR can achieve good predictive performance, and then (2) generating a quantum state encoding the optimal fitting parameters of RR with suchα, which can be further utilized to predict new data. Since indefinite dense Hamiltonian simulation has been adopted as a key subroutine, our algorithm can efficiently handle non-sparse data matrices. It is shown that our algorithm can achieve exponential speedup over the classical counterpart for (low-rank) data matrices with low condition numbers. But when the condition numbers of data matrices are large to be amenable to full or approximately full ranks of data matrices, only polynomial speedup can be achieved.
We propose a quantum data fitting algorithm for non-sparse matrices, which is based on the Quantum Singular Value Estimation (QSVE) subroutine and a novel efficient method for recovering the signs of eigenvalues. Our algorithm generalizes the quantum data fitting algorithm of Wiebe, Braun, and Lloyd for sparse and well-conditioned matrices by adding a regularization term to avoid the over-fitting problem, which is a very important problem in machine learning. As a result, the algorithm achieves a sparsity-independent runtime of O(κ2Npolylog(N)/(εlogκ)) for an N×N dimensional Hermitian matrix F, where κ denotes the condition number of F and ε is the precision parameter. This amounts to a polynomial speedup on the dimension of matrices when compared with the classical data fitting algorithms, and a strictly less than quadratic dependence on κ.
With the significant advancement in quantum computation during the past couple of decades, the exploration of machine-learning subroutines using quantum strategies has become increasingly popular. Gaussian process regression is a widely used technique in supervised classical machine learning. Here we introduce an algorithm for Gaussian process regression using continuous-variable quantum systems that can be realized with technology based on photonic quantum computers under certain assumptions regarding distribution of data and availability of efficient quantum access. Our algorithm shows that by using a continuous-variable quantum computer a dramatic speedup in computing Gaussian process regression can be achieved, i.e., the possibility of exponentially reducing the time to compute. Furthermore, our results also include a continuous-variable quantum-assisted singular value decomposition method of nonsparse low rank matrices and forms an important subroutine in our Gaussian process regression algorithm.
Linear regression is a widely used technique to fit linear models and finds widespread applications across different areas such as machine learning and statistics. In most real-world scenarios, however, linear regression problems are often ill-posed or the underlying model suffers from o v e r f i t t i n g , leading to erroneous or trivial solutions. This is often dealt with by adding extra constraints, known as regularization. In this paper, we use the frameworks of block-encoding and quantum singular value transformation (QSVT) to design the first quantum algorithms for quantum least squares with general ℓ 2 -regularization. These include regularized versions of quantum ordinary least squares, quantum weighted least squares, and quantum generalized least squares. Our quantum algorithms substantially improve upon prior results on quantum ridge regression (polynomial improvement in the condition number and an exponential improvement in accuracy), which is a particular case of our result.To this end, we assume approximate block-encodings of the underlying matrices as input and use robust QSVT algorithms for various linear algebra operations. In particular, we develop a variable-time quantum algorithm for matrix inversion using QSVT, where we use quantum eigenvalue discrimination as a subroutine instead of gapped phase estimation. This ensures that substantially fewer ancilla qubits are required for this procedure than prior results. Owing to the generality of the block-encoding framework, our algorithms are applicable to a variety of input models and can also be seen as improved and generalized versions of prior results on standard (non-regularized) quantum least squares algorithms.
Graph kernels are essential for learning the properties of graph data, a fundamental task in the analysis of such data. However, a major limitation of current graph kernel methods is their high computational cost, which becomes prohibitive when dealing with large-scale graphs. In order to address this bottleneck, we propose a quantum algorithm designed to analyze the intrinsic structural information within graph data through an efficient quantum kernel method. The core idea of our kernel method involves encoding pertinent information from graphs into quantum states, utilizing quantum kernel functions to represent the similarities among various graphs. This process is facilitated through the application of quantum walks and quantum signal processing techniques. Building upon this framework, we propose a quantum kernel ridge regression algorithm that consists of two key steps. First, we employ our quantum kernel method to prepare a quantum state, in which the amplitudes encode the kernel functions. Second, we implement quantum feature mapping in parallel to encode the corresponding kernel matrix into the quantum circuit. Crucially, we demonstrate that the computational complexity of our regression algorithm scales primarily as O(M3/2) with respect to the size of the graph set M. This suggests that our quantum kernel method could process graph data with resource requirements scaling approximately as O(polylog(N)), where N denotes the number of nodes in the graph. Accordingly, this underscores the advantage of our approach over classical methods in the context of large-scale graph analysis. To validate our approach, we conduct numerical experiments on chemical molecular datasets, demonstrating the method's effectiveness and advantages. In summary, this work represents a significant advancement in quantum graph learning, enhancing its potential for analyzing large-scale graph data.
Spectral clustering is one of the most robust methods of an unsupervised machine learning field. Compared with the well-known k-means, spectral clustering uses the spectral properties of the Laplacian matrix to project data to a low-dimensional clustering with higher efficiency. However, for a sparse network with a substantial degree of heterogeneity, standard spectral clustering often overfits noise in the periphery of a sparse and stochastic graph. In our work, we combined the quantum version of the k-means algorithm with regularized spectral clustering and proposed a new quantum machine learning algorithm. It is more like a combination of classical and quantum algorithms. Compared with the established quantum k-means algorithm, our method has obvious computational advantages in non-convex or nested structures. At this stage, the research of quantum algorithms mainly stays in the simulation of classical computers. Our method does not need to expend a lot of effort to preprocess the data at the initial quantum state stage. Under the assumption of quantum data encoding, we theoretically demonstrate the feasibility of the quantum regularized spectral clustering algorithm. Then combine Q-means algorithm complexity advantages to complete the clustering task. This work aims to pave the path and help realize quantum spectral clustering algorithms on real quantum computers in the future and help create other versions of quantum machine learning algorithms. We provide simulations and data examples to illustrate these results.