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

arXiv:1707.09524 · IEEE Transactions on Knowledge and Data Engineering

An improved quantum algorithm for ridge regression

Chao-Hua Yu, Fei Gao, Qiaoyan Wen

Published Jan 1, 2019• 95 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tkde.2019.2937491

Related papers

Quantum algorithms for ridge regression

Chao‐Hua Yu, Fei Gao, Qiaoyan Wen

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.

•Jul 29, 2017•6 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 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

Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters

Zhao Song, Junze Yin, Ruizhe Zhang

Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix $A \in \mathbb{R}^{n \times d}$ and a vector $b$, the goal is to find $x'$ such that $ \| Ax' - b \|_2^2 \leq (1+ε) \min_{x} \| A x - b \|_2^2 $. The best classical algorithm takes $O(nd) + \mathrm{poly}(d/ε)$ time [Clarkson and Woodruff STOC 2013, Nelson and Nguyen FOCS 2013]. On the other hand, quantum linear regression algorithms can achieve exponential quantum speedups, as shown in [Wang Phys. Rev. A 96, 012335, Kerenidis and Prakash ITCS 2017, Chakraborty, Gily{é}n and Jeffery ICALP 2019]. However, the running times of these algorithms depend on some quantum linear algebra-related parameters, such as $κ(A)$, the condition number of $A$. In this work, we develop a quantum algorithm that runs in $\widetilde{O}(ε^{-1}\sqrt{n}d^{1.5}) + \mathrm{poly}(d/ε)$ time. It provides a quadratic quantum speedup in $n$ over the classical lower bound without any dependence on data-dependent parameters. In addition, we also show our result can be generalized to multiple regression and ridge linear regression.

arXiv:2311.14823•Nov 24, 2023•0 citations

Quantum algorithm for low-rank matrix regression with feature extraction

Kaitian Gao, Youlong Yang, Zhenye Du

Low-rank matrix regression is a pivotal technique in image processing and pattern recognition that can directly handle data with intrinsic matrix structures. However, classical algorithms for this task suffer from a computational bottleneck, where the complexity escalates cubically with the matrix dimension, incurring prohibitive costs for high-dimensional datasets. In this study, we propose a quantum algorithm for low-rank matrix regression with feature extraction, leveraging the Harrow–Hassidim–Lloyd algorithm for regression matrix estimation and a modified quantum singular-value thresholding algorithm for iterative variable updates. Theoretical analysis demonstrates that our algorithm reduces the time complexity dependence on the matrix dimension from cubic to logarithmic, achieving an exponential speedup over classical counterparts when the problem is well conditioned and the precision requirements are moderate. Furthermore, we introduce an algorithmic variant utilizing the quantum memory model to bypass the reliance on quantum random access memory. Additionally, we propose a hybrid strategy leveraging quantum sketching techniques to effectively eliminate the runtime dependence on the condition number. Subsequently, we performed small-scale quantum experiments to validate the feasibility of our proposed quantum algorithm.

Journal of Applied Physics•Jan 5, 2026•0 citations
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.
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.
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.
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.
Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix A∈Rn×dA \in \mathbb{R}^{n \times d}A∈Rn×d and a vector bbb, the goal is to find x′x'x′ such that $ \| Ax' - b \|_2^2 \leq (1+ε) \min_{x} \| A x - b \|_2^2 $. The best classical algorithm takes O(nd)+poly(d/ε)O(nd) + \mathrm{poly}(d/ε)O(nd)+poly(d/ε) time [Clarkson and Woodruff STOC 2013, Nelson and Nguyen FOCS 2013]. On the other hand, quantum linear regression algorithms can achieve exponential quantum speedups, as shown in [Wang Phys. Rev. A 96, 012335, Kerenidis and Prakash ITCS 2017, Chakraborty, Gily{é}n and Jeffery ICALP 2019]. However, the running times of these algorithms depend on some quantum linear algebra-related parameters, such as κ(A)κ(A)κ(A), the condition number of AAA. In this work, we develop a quantum algorithm that runs in O~(ε−1nd1.5)+poly(d/ε)\widetilde{O}(ε^{-1}\sqrt{n}d^{1.5}) + \mathrm{poly}(d/ε)O(ε−1n​d1.5)+poly(d/ε) time. It provides a quadratic quantum speedup in nnn over the classical lower bound without any dependence on data-dependent parameters. In addition, we also show our result can be generalized to multiple regression and ridge linear regression.
Low-rank matrix regression is a pivotal technique in image processing and pattern recognition that can directly handle data with intrinsic matrix structures. However, classical algorithms for this task suffer from a computational bottleneck, where the complexity escalates cubically with the matrix dimension, incurring prohibitive costs for high-dimensional datasets. In this study, we propose a quantum algorithm for low-rank matrix regression with feature extraction, leveraging the Harrow–Hassidim–Lloyd algorithm for regression matrix estimation and a modified quantum singular-value thresholding algorithm for iterative variable updates. Theoretical analysis demonstrates that our algorithm reduces the time complexity dependence on the matrix dimension from cubic to logarithmic, achieving an exponential speedup over classical counterparts when the problem is well conditioned and the precision requirements are moderate. Furthermore, we introduce an algorithmic variant utilizing the quantum memory model to bypass the reliance on quantum random access memory. Additionally, we propose a hybrid strategy leveraging quantum sketching techniques to effectively eliminate the runtime dependence on the condition number. Subsequently, we performed small-scale quantum experiments to validate the feasibility of our proposed quantum algorithm.