An improved quantum-inspired algorithm for linear regression

• URL: http://arxiv.org/abs/2009.07268v4
• Date: Mon, 27 Jun 2022 02:08:07 GMT
• Title: An improved quantum-inspired algorithm for linear regression
• Authors: Andr\'as Gily\'en and Zhao Song and Ewin Tang
• Abstract summary: We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm. We show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting.
• Score: 15.090593955414137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09, arXiv:0811.3171] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18, arXiv:1704.06174], when the input matrix $A$ is stored in a data structure applicable for QRAM-based state preparation. Namely, suppose we are given an $A \in \mathbb{C}^{m\times n}$ with minimum non-zero singular value $\sigma$ which supports certain efficient $\ell_2$-norm importance sampling queries, along with a $b \in \mathbb{C}^m$. Then, for some $x \in \mathbb{C}^n$ satisfying $\|x - A^+b\| \leq \varepsilon\|A^+b\|$, we can output a measurement of $|x\rangle$ in the computational basis and output an entry of $x$ with classical algorithms that run in $\tilde{\mathcal{O}}\big(\frac{\|A\|_{\mathrm{F}}^6\|A\|^6}{\sigma^{12}\varepsilon^4}\big)$ and $\tilde{\mathcal{O}}\big(\frac{\|A\|_{\mathrm{F}}^6\|A\|^2}{\sigma^8\varepsilon^4}\big)$ time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of $\frac{\|A\|^{16}}{\sigma^{16}\varepsilon^2}$ [Chia, Gily\'en, Li, Lin, Tang, and Wang, STOC'20, arXiv:1910.06151]. As a consequence, we show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting and related settings. Our work applies techniques from sketching algorithms and optimization to the quantum-inspired literature. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired settings, for comparison against future quantum computers.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters [10.602399256297032]
  We develop a quantum algorithm that runs in $widetildeO(epsilon-1sqrtnd1.5) + mathrmpoly(d/epsilon)$ time. It provides a quadratic quantum speedup in $n over the classical lower bound without any dependence on data-dependent parameters.
  arXiv  Detail & Related papers  (2023-11-24T19:41:28Z)
• Quantum speedups for linear programming via interior point methods [1.8434042562191815]
  We describe a quantum algorithm for solving a linear program with $n$ inequality constraints on $d$ variables. Our algorithm speeds up the Newton step in the state-of-the-art interior point method of Lee and Sidford.
  arXiv  Detail & Related papers  (2023-11-06T16:00:07Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems [11.929584800629673]
  We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems.
  arXiv  Detail & Related papers  (2023-07-13T08:46:19Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Quantum machine learning with subspace states [8.22379888383833]
  We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum sampling algorithm that samples from the distribution $Pr[S]= det(X_SX_ST)$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(dlog n)$. The second is a quantum singular value estimation algorithm for compound matrices $mathcalAk$, the speedup for this algorithm is potentially exponential.
  arXiv  Detail & Related papers  (2022-01-31T19:34:47Z)
• Faster quantum-inspired algorithms for solving linear systems [0.05076419064097732]
  We show that there is a classical algorithm that outputs a data structure for $x$ allowing sampling and querying to the entries. This output can be viewed as a classical analogue to the output of quantum linear solvers.
  arXiv  Detail & Related papers  (2021-03-18T15:12:44Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.