Abstract
Linear regression is a widely used technique to fit linear models and finds widespread applications across different
areas of natural sciences, as well as field 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.
For instance, suppose that we are given N data points {(ai
, bi)}
N
i=1 where ∀i : ai ∈ R
d
, ∀i : bi ∈ R. The
assumption is that there is a vector x such that bi = x
T ai +ei
, where ei
is a random variable (noise) with mean
0. Suppose A is the data matrix of dimension N × d, such that its i
th row is the vector ai and b ∈ R
N such
that b = (b1, · · · , bN )
T
. Adding an ℓ2-regularization, the objective is to obtain x that minimizes
∥Ax − b∥
2
2 + λ∥Lx∥
2
2
(0.0.1)
where L is an appropriately chosen penalty matrix (or regularization matrix) of dimension N ×d and λ > 0 is the
regularization parameter, an appropriately chosen constant. This regularization technique is known as general
ℓ2 -regularization in the literature. It is a generalization of the well known ridge regression which corresponds
to the case when L is the identity matrix. The closed-form solution of the general ℓ2-regularized ordinary least
squares problem is given by
x =
A
T A + λLTL
−1
A
T
b. (0.0.2)
A straightforward observation is that even when AT A is singular, regularization ensures that the condition
number (ratio of the maximum and the minimum singular values) of the resulting matrix is finite and therefore
AT A + λLTL is invertible. Another observation is that when the condition number of A is arbitrarily large
(the minimum singular value of A is arbitrarily small), the condition number of the matrix to be inverted in
Equation 0.0.2 can be tamed significantly. Since the complexity of most quantum algorithms for the quantum
versions of these problems depend the condition number, the complexity reduces significantly. These models can
be generalized to situations where the data points are weighted or correlated which incorporate more realistic
scenarios.
Quantum linear systems solvers are possibly among the most studied quantum algorithms. In this work we
develop the first quantum algorithms for ordinary, weighted and generalized least squares with generalized ℓ2-
regularization. We assume access to (approximate) block-encodings of the relevant matrices and develop robust
versions of quantum singular value transformations to implement linear transformations of these matrices. Our
goal is to output a quantum state that is δ-close to |x⟩, the state encoding the solution to the underlying
regularized least squares problem. Owing to the generality of the block-encoding framework, our algorithms are
applicable to a variety of input models. In order to obtain our results, we work with approximate block-encodings
of matrices and apply robust quantum singular value transformations (QSVT) to them. For most quantum
linear algebra applications using QSVT, access to perfect block-encoding is assumed, and the robustness of such
algorithms is left out.
We develop a space-efficient variable time amplitude amplification (VTAA) procedure, which we then use in
a variable-time matrix inversion algorithm. A crucial requirement for variable time matrix inversion algorithm
is the application of the inversion procedure to the portion of the input state that is spanned by singular values
larger than a certain threshold. In order to achieve this, prior results have made use of Gapped Phase Estimation
(GPE), which is a simple variant of the standard phase estimation procedure. However, GPE requires extra
registers that store the estimates of the phases, which are never used in the variable-time algorithm. In this
work, instead of GPE, we make use of a robust version of quantum eigenvalue discrimination (QEVD) using
QSVT, which decides whether the eigenvalue of a matrix is above or below a certain threshold without storing
the eigenvalue estimates. Given the block-encoding of a matrix A with condition number κ, this procedure
for implementing A+ reduces the number of additional qubits required for our variable time by a factor of
O(log2
(κ/δ)) as compared to prior results, where δ is the desired accuracy. We show that in order to implement
A+, the precision required in the block-encoding of A is determined in turn by the precision in the QEVD procedure. Consequently, this improves both variable-time amplitude amplification and quantum linear systems
algorithm: we achieve optimal complexity (linear dependence in the condition number and polylogarithmic
dependence on inverse-accuracy) using far fewer ancilla qubits. We then use this to develop our algorithms
for ordinary, weighted and generali
