An improved quantum algorithm for ridge regression

Ridge regression (RR) is an important machine learning technique which\nintroduces a regularization hyperparameter $\\alpha$ to ordinary multiple linear\nregression for analyzing data suffering from multicollinearity. In this paper,\nwe present a quantum algorithm for RR, where the technique of parallel\nHamiltonian simulation to simulate a number of Hermitian matrices in parallel\nis proposed and used to develop a quantum version of $K$-fold cross-validation\napproach, which can efficiently estimate the predictive performance of RR. Our\nalgorithm consists of two phases: (1) using quantum $K$-fold cross-validation\nto efficiently determine a good $\\alpha$ with which RR can achieve good\npredictive performance, and then (2) generating a quantum state encoding the\noptimal fitting parameters of RR with such $\\alpha$, which can be further\nutilized to predict new data. Since indefinite dense Hamiltonian simulation has\nbeen adopted as a key subroutine, our algorithm can efficiently handle\nnon-sparse data matrices. It is shown that our algorithm can achieve\nexponential speedup over the classical counterpart for (low-rank) data matrices\nwith low condition numbers. But when the condition numbers of data matrices is\nlarge to be amenable to full or approximately full ranks of data matrices, only\npolynomial speedup can be achieved.\n