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:2104.13108

Quantum Algorithms for Prediction Based on Ridge Regression

Menghan Chen, Chao‐Hua Yu, Gongde Guo, Song Lin

Published Apr 27, 2021• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2104.13108

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

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 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 algorithm for Gaussian process regression

Menghan Chen, Chao‐Hua Yu, Jianliang Gao +4 more

The Gaussian process is a widely used model for regression problems in supervised machine learning. However, predicting new inputs via a Gaussian process model becomes computationally inefficient when training a large data set. This paper proposes a fast quantum algorithm for prediction based on the Gaussian process regression. The proposed quantum algorithm consists of two subalgorithms: the first one aims to efficiently prepare the squared exponential covariance matrices and covariance functions vector with annihilation and creation operators; the other is to obtain predictive mean values and covariance values for new inputs. Evidence is also shown that the proposed quantum Gaussian process regression algorithm can achieve quadratic speedup over the classical counterpart.

Physical Review A•Jul 5, 2022•20 citations

Quantum Gaussian process regression

Menghan Chen, Gongde Guo, Song Lin +1 more

In this paper, a quantum algorithm based on gaussian process regression model is proposed. The proposed quantum algorithm consists of three sub-algorithms. One is the first quantum subalgorithm to efficiently generate mean predictor. The improved HHL algorithm is proposed to obtain the sign of outcomes. Therefore, the terrible situation that results is ambiguous in terms of original HHL algorithm is avoided, which makes whole algorithm more clear and exact. The other is to product covariance predictor with same method. Thirdly, the squared exponential covariance matrices are prepared that annihilation operator and generation operator are simulated by the unitary linear decomposition Hamiltonian simulation and kernel function vectors is generated with blocking coding techniques on covariance matrices. In addition, it is shown that the proposed quantum gaussian process regression algorithm can achieve quadratic faster over the classical counterpart.

arXiv:2106.06701•Jun 12, 2021•0 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
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.
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.
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.
The Gaussian process is a widely used model for regression problems in supervised machine learning. However, predicting new inputs via a Gaussian process model becomes computationally inefficient when training a large data set. This paper proposes a fast quantum algorithm for prediction based on the Gaussian process regression. The proposed quantum algorithm consists of two subalgorithms: the first one aims to efficiently prepare the squared exponential covariance matrices and covariance functions vector with annihilation and creation operators; the other is to obtain predictive mean values and covariance values for new inputs. Evidence is also shown that the proposed quantum Gaussian process regression algorithm can achieve quadratic speedup over the classical counterpart.
In this paper, a quantum algorithm based on gaussian process regression model is proposed. The proposed quantum algorithm consists of three sub-algorithms. One is the first quantum subalgorithm to efficiently generate mean predictor. The improved HHL algorithm is proposed to obtain the sign of outcomes. Therefore, the terrible situation that results is ambiguous in terms of original HHL algorithm is avoided, which makes whole algorithm more clear and exact. The other is to product covariance predictor with same method. Thirdly, the squared exponential covariance matrices are prepared that annihilation operator and generation operator are simulated by the unitary linear decomposition Hamiltonian simulation and kernel function vectors is generated with blocking coding techniques on covariance matrices. In addition, it is shown that the proposed quantum gaussian process regression algorithm can achieve quadratic faster over the classical counterpart.
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.