  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 overfitting, 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
$\ell_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.
