Quantum Algorithm for Linear Regression

Abstract

We present a quantum algorithm for fitting a linear regression model to a given data set using the least squares approach. Different from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\mathrm{poly}(\log (N),d,\kappa ,1/\epsilon )$, where $N$ is the size of the data set, $d$ is the number of adjustable parameters, $\kappa$ is the condition number of the design matrix, and $\epsilon$ is the desired precision in the output. We also show that the polynomial dependence on $d$ and $\kappa$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.

22 pages, no figure. Final version

References in corpus (23)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• An introduction to quantum machine learning
• Exponential algorithmic speedup by quantum walk
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Quantum Data Fitting
• Quantum-enhanced machine learning
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Prediction by linear regression on a quantum computer
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Quantum speedup for active learning agents
• Application of Quantum Annealing to Training of Deep Neural Networks
• Simulating a perceptron on a quantum computer
• Bayesian Network Structure Learning Using Quantum Annealing
• Simulating sparse Hamiltonians with star decompositions
• Quantum Hamiltonian Learning Using Imperfect Quantum Resources
• Quantum Recommendation Systems
• Quantum learning of coherent states
• Reinforcement Learning Using Quantum Boltzmann Machines

Cited by in corpus (55)

• Quantum computing for finance: overview and prospects
• Quantum computing for finance
• Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers
• The prospects of quantum computing in computational molecular biology
• Quantum Machine Learning for Chemistry and Physics
• Quantum singular value decomposition of non-sparse low-rank matrices
• Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
• Quantum-assisted Helmholtz machines: A quantum-classical deep learning framework for industrial datasets in near-term devices
• Quantum data compression by principal component analysis
• Adiabatic Quantum Linear Regression
• Hamiltonian Simulation with Optimal Sample Complexity
• Quantum K-nearest neighbor classification algorithm based on Hamming distance
• Quantum Algorithms for Compositional Natural Language Processing
• Quantum algorithm for visual tracking
• Quantum Machine Learning for Finance
• Machine learning \& artificial intelligence in the quantum domain
• Variational Quantum Algorithms for Dimensionality Reduction and Classification
• Improved quantum algorithm for A-optimal projection
• A Grover-search Based Quantum Learning Scheme for Classification
• Quantum algorithms for anomaly detection using amplitude estimation
• Quantum Differentially Private Sparse Regression Learning
• A brief introduction to quantum algorithms
• How quantum computing can enhance biomarker discovery
• Quantum algorithm for Neighborhood Preserving Embedding
• Quantum Regularized Least Squares
• Quantum Algorithms to Matrix Multiplication
• Quantum advantage for differential equation analysis
• Realizing quantum linear regression with auxiliary qumodes
• Quantum algorithms for scientific computing
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test
• What can we learn from quantum convolutional neural networks?
• Experimental implementation of quantum algorithm for association rules mining
• Quantum mean centering for block-encoding-based quantum algorithm
• Quantum Algorithm for Unsupervised Anomaly Detection
• Quantum Gaussian process model of potential energy surface for a polyatomic molecule
• Communication-efficient Quantum Algorithm for Distributed Machine Learning
• Quantum algorithms for SVD-based data representation and analysis
• Statistical Limits of Supervised Quantum Learning
• Quantum Approximate Optimization Algorithm for Maximum Likelihood Detection in Massive MIMO
• Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
• From linear combination of quantum states to Grover's searching algorithm
• Quantum algorithm for logistic regression
• Quantum Algorithms for the Pathwise Lasso
• Inverse iteration quantum eigensolvers assisted with a continuous variable
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Adaptive Random Quantum Eigensolver
• Strong nonlocal sets of UPB
• The Learnability of Unknown Quantum Measurements
• Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL
• The Abstract Structure of Quantum Algorithms
• Benchmarking of quantum fidelity kernels for Gaussian process regression
• Ensuring superior learning outcomes and data security for authorized learner
• Quantum Regularized Least Squares Solver with Parameter Estimate
• Quantum Machine Learning For Classical Data
• Quantum Algorithm to Cubic Spline Interpolation