Quantum Algorithms for Regularized Linear Regression 

The problem of fitting a theoretical model to a large set of experimental data, known as linear regression, finds applications across disciplines, ranging from the natural sciences to machine learning and statistics. One popular method is the least squares regression technique, which constructs the best linear fit to the series of data points while minimizing the sum of squared errors. However, often, this approach runs into frequent problems leading to trivial or erroneous solutions. As a result, in most practical scenarios, the method of regularized least squares is employed, a generalization of the standard least squares approach and its variants. Indeed, regularized versions of ordinary, weighted, and generalized least squares have found wide applicability in the classical machine learning literature. 

In this work, we develop the first quantum algorithms for ordinary, weighted, and generalized least squares, with general ℓ2-regularization. As with most problems in quantum machine learning, our quantum algorithms output a quantum state proportional to the corresponding classical solution of the problem. A particular case of our method is the problem of quantum ridge regression, for which our approach offers an exponential advantage in precision over prior quantum algorithms. Our results can also be seen as improved and generalized versions of prior results on quantum linear regression.

The main technical tools we make use of are robust versions of state-of-the-art techniques from quantum linear algebra, such as quantum singular value transformation and the framework of block-encoding. Additionally, we also develop quantum algorithmic primitives that are of independent interest. For instance, we develop a robust procedure for quantum singular value discrimination: this procedure determines whether the singular values of a matrix are above or below a certain threshold. We show that this subroutine drastically reduces the number of ancilla qubits required for performing variable-time amplitude amplification and, consequently, for solving quantum linear systems with optimal complexity. Our work serves as a concrete example of how techniques from quantum linear algebra can help solve useful problems in machine learning.  

Publication: S. Chakraborty, A. Morolia, and A. Peduri, Quantum Regularized Least Squares,  Quantum 7, 988 (2023). arXiv.