Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization

Abstract

Linear regression is a basic and widely-used methodology in data analysis. It is known that some quantum algorithms efficiently perform least squares linear regression of an exponentially large data set. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error $\epsilon$: the best one among the existing proposals is $O({\epsilon }^{-2})$. In this paper, we propose the new quantum algorithm for linear regression, which has the complexity of $O({\epsilon }^{-1})$ and keeps the logarithmic dependence on the number of data points $N_D$. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have the complexity proportional to $N_D$, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.

arXiv comment13 pages, no figure

References in corpus (19)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Quantum Data Fitting
• Quantum speedup of Monte Carlo methods
• Architectures for a quantum random access memory
• Prediction by linear regression on a quantum computer
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Amplitude estimation without phase estimation
• Option Pricing using Quantum Computers
• Iterative Quantum Amplitude Estimation
• Quantum gradient descent for linear systems and least squares
• Quantum Algorithm for Linear Regression
• Quantum Approximate Counting, Simplified
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• An improved quantum-inspired algorithm for linear regression
• Faster Amplitude Estimation
• Quantum Amplitude Estimation in the Presence of Noise
• Quantum algorithm for logistic regression
• Faster quantum-inspired algorithms for solving linear systems

Cited by in corpus (4)

• Quantum Fourier Iterative Amplitude Estimation
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• Quantum Algorithms for the Pathwise Lasso
• Benchmarking of quantum fidelity kernels for Gaussian process regression