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:1601.07823 · Physical Review A

Prediction by linear regression on a quantum computer

Maria Schuld, Ilya Sinayskiy, Francesco Petruccione

Published Aug 30, 2016• 293 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.94.022342

Related papers

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•159 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•40 citations

Quantum Algorithms for Solving Linear Regression Equation

Kai Li, Hong‐Yi Dai, Jing Feng +4 more

Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.

Journal of Physics Conference Series•Jan 1, 2021•6 citations

Continuous-variable quantum Gaussian process regression and quantum singular value decomposition of nonsparse low-rank matrices

Siddhartha Das, George Siopsis, Christian Weedbrook

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.

arXiv:1707.00360•Physical Review A•Feb 12, 2018•29 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

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•26 citations
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.
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.
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.
Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.
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.
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.
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.