Quantum Algorithms for Regularized Least Squares

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 generalized least squares with general ℓ2-regularization. The primitives we have developed, and our approach to designing the algorithms might be of independent interest to the community, specially in the domain of quantum machine learning (QML) and quantum algorithms for natural sciences, where such quantum linear algebra subroutines (QLAS) are frequently used.