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 algorithms for ridge regression

Chao‐Hua Yu, Fei Gao, Qiaoyan Wen

Published Jul 29, 2017• 6 citations
OpenAlex

Abstract

Ridge regression (RR), also called regularized linear regression, is an important machine learning technique which introduces a regularization hyperparameter to ordinary multiple linear regression for analyzing data suffering from multicollinearity. Here we provide an efficient quantum algorithm for RR. Specifically, by giving the technique of parallel Hamiltonian simulation that can simulate a number of Hermitian matrices in parallel, we develop a quantum version of $K$-fold cross-validation approach that can efficiently estimate the predictive performance of RR. Our algorithm involves two phases: (1) we first use the quantum $K$-fold cross-validation to efficiently determine an approximately optimal regularization hyperparameter for RR with which RR can achieve very good predictive performance, and (2) then generate a quantum state encoding the optimal fitting parameters of RR with such hyperparameter, which can be further utilized to predict new data. Our algorithm can handle nonsparse data matrices, and is exponentially faster than the classical algorithm for (low-rank) design matrices with relatively small elements and low condition numbers.

Related papers

An improved quantum algorithm for ridge regression

Chao-Hua Yu, Fei Gao, Qiaoyan Wen

Ridge regression (RR) is an important machine learning technique which introduces a regularization hyperparameter$\alpha$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 of$K$-fold cross-validation approach, which can efficiently estimate the predictive performance of RR. Our algorithm consists of two phases: (1) using quantum$K$-fold cross-validation to efficiently determine a good$\alpha$with which RR can achieve good predictive performance, and then (2) generating a quantum state encoding the optimal fitting parameters of RR with such$\alpha$, 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.

arXiv:1707.09524•IEEE Transactions on Knowledge and Data Engineering•Jan 1, 2019•95 citations

Quantum Algorithms for Prediction Based on Ridge Regression

Menghan Chen, Chao‐Hua Yu, Gongde Guo +1 more

We propose a quantum algorithm based on ridge regression model, which get the optimal fitting parameters w and a regularization hyperparameter α by analysing the training dataset. The algorithm consists of two subalgorithms. One is generating predictive value for a new input, the way is to apply the phase estimation algorithm to the initial state |Xi and apply the controlled rotation to the eigenvalue register. The other is finding an optimal regularization hyperparameter α , the way is to apply the phase estimation algorithm to the initial state |yi and apply the controlled rotation to the eigenvalue register. The second subalgorithm can compute the whole training dataset in parallel that improve the efficiency. Compared with the classical ridge regression algorithm, our algorithm overcome multicollinearity and overfitting. Moreover, it have exponentially faster. What's more, our algorithm can deal with the non-sparse matrices in comparison to some existing quantum algorithms and have slightly speedup than the existing quantum counterpart. At present, the quantum algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.

arXiv:2104.13108•Apr 27, 2021•0 citations

Quantum algorithm for linear regression

Guoming Wang

We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where $N$ is the size of the data set, $d$ is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on $d$ and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.

arXiv:1402.0660•Physical Review A•Jul 31, 2017•144 citations

Quantum Algorithm for Spectral Regression for Regularized Subspace Learning

Fan‐Xu Meng, Xutao Yu, Rui-Qing Xiang +1 more

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.

IEEE Access•Dec 13, 2018•7 citations

Quantum Regularized Least Squares

Shantanav Chakraborty, Aditya Morolia, Anurudh Peduri

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.

arXiv:2206.13143•Quantum•Apr 27, 2023•22 citations

Prediction by linear regression on a quantum computer

Maria Schuld, Ilya Sinayskiy, Francesco Petruccione

We give an algorithm for prediction on a quantum computer which is based on a linear regression model with least-squares optimization. In contrast to related previous contributions suffering from the problem of reading out the optimal parameters of the fit, our scheme focuses on the machine-learning task of guessing the output corresponding to a new input given examples of data points. Furthermore, we adapt the algorithm to process nonsparse data matrices that can be represented by low-rank approximations, and significantly improve the dependency on its condition number. The prediction result can be accessed through a single-qubit measurement or used for further quantum information processing routines. The algorithm's runtime is logarithmic in the dimension of the input space provided the data is given as quantum information as an input to the routine.

arXiv:1601.07823•Physical Review A•Aug 30, 2016•277 citations
Ridge regression (RR), also called regularized linear regression, is an important machine learning technique which introduces a regularization hyperparameter to ordinary multiple linear regression for analyzing data suffering from multicollinearity. Here we provide an efficient quantum algorithm for RR. Specifically, by giving the technique of parallel Hamiltonian simulation that can simulate a number of Hermitian matrices in parallel, we develop a quantum version of KKK-fold cross-validation approach that can efficiently estimate the predictive performance of RR. Our algorithm involves two phases: (1) we first use the quantum KKK-fold cross-validation to efficiently determine an approximately optimal regularization hyperparameter for RR with which RR can achieve very good predictive performance, and (2) then generate a quantum state encoding the optimal fitting parameters of RR with such hyperparameter, which can be further utilized to predict new data. Our algorithm can handle nonsparse data matrices, and is exponentially faster than the classical algorithm for (low-rank) design matrices with relatively small elements and low condition numbers.
Ridge regression (RR) is an important machine learning technique which introduces a regularization hyperparameterα\alphaα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 ofKKK-fold cross-validation approach, which can efficiently estimate the predictive performance of RR. Our algorithm consists of two phases: (1) using quantumKKK-fold cross-validation to efficiently determine a goodα\alphaαwith which RR can achieve good predictive performance, and then (2) generating a quantum state encoding the optimal fitting parameters of RR with suchα\alphaα, 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 algorithm based on ridge regression model, which get the optimal fitting parameters w and a regularization hyperparameter α by analysing the training dataset. The algorithm consists of two subalgorithms. One is generating predictive value for a new input, the way is to apply the phase estimation algorithm to the initial state |Xi and apply the controlled rotation to the eigenvalue register. The other is finding an optimal regularization hyperparameter α , the way is to apply the phase estimation algorithm to the initial state |yi and apply the controlled rotation to the eigenvalue register. The second subalgorithm can compute the whole training dataset in parallel that improve the efficiency. Compared with the classical ridge regression algorithm, our algorithm overcome multicollinearity and overfitting. Moreover, it have exponentially faster. What's more, our algorithm can deal with the non-sparse matrices in comparison to some existing quantum algorithms and have slightly speedup than the existing quantum counterpart. At present, the quantum algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.
We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where NNN is the size of the data set, ddd is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on ddd and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.
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.
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.
We give an algorithm for prediction on a quantum computer which is based on a linear regression model with least-squares optimization. In contrast to related previous contributions suffering from the problem of reading out the optimal parameters of the fit, our scheme focuses on the machine-learning task of guessing the output corresponding to a new input given examples of data points. Furthermore, we adapt the algorithm to process nonsparse data matrices that can be represented by low-rank approximations, and significantly improve the dependency on its condition number. The prediction result can be accessed through a single-qubit measurement or used for further quantum information processing routines. The algorithm's runtime is logarithmic in the dimension of the input space provided the data is given as quantum information as an input to the routine.