Quantum Regularized Least Squares

Abstract

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.

arXiv comment51 pages. Accepted in Quantum Journal

References in corpus (23)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Data Fitting
• A Grand Unification of Quantum Algorithms
• Prediction by linear regression on a quantum computer
• A quantum-inspired classical algorithm for recommendation systems
• Near-optimal ground state preparation
• Quantum gradient descent for linear systems and least squares
• The methodology of resonant equiangular composite quantum gates
• Quantum Algorithm for Linear Regression
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Lecture notes on ridge regression
• Hamiltonian Simulation in the Interaction Picture
• An improved quantum-inspired algorithm for linear regression
• Hamiltonian Simulation by Uniform Spectral Amplification
• Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle

Cited by in corpus (7)

• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems
• Quantum Next Generation Reservoir Computing: An Efficient Quantum Algorithm for Forecasting Quantum Dynamics
• Quantum Algorithms for the Pathwise Lasso
• Quantum linear system algorithm with optimal queries to initial state preparation
• Benchmarking of quantum fidelity kernels for Gaussian process regression
• Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers