---
abstract: 'We present classical sublinear-time algorithms for solving low-rank linear systems of equations. Our algorithms are inspired by the HHL quantum algorithm @HHL09 for solving linear systems and the recent breakthrough by Tang @T18 of dequantizing the quantum algorithm for recommendation systems. Let $A \in \mathbb{C}^{m \times n}$ be a rank-$k$ matrix, and $b \in \mathbb{C}^m$ be a vector. We present two algorithms: a "sampling" algorithm that provides a sample from $A^{-1}b$ and a "query" algorithm that outputs an estimate of an entry of $A^{-1}b$, where $A^{-1}$ denotes the Moore-Penrose pseudo-inverse. Both of our algorithms have query and time complexity $O(\mathrm{poly}(k, \kappa, \|A\|_F, 1/\epsilon)\,\mathrm{polylog}(m, n))$, where $\kappa$ is the condition number of $A$ and $\epsilon$ is the precision parameter. Note that the algorithms we consider are sublinear time, so they cannot write and read the whole matrix or vectors. In this paper, we assume that $A$ and $b$ come with well-known low-overhead data structures such that entries of $A$ and $b$ can be sampled according to some natural probability distributions. Alternatively, when $A$ is positive semidefinite, our algorithms can be adapted so that the sampling assumption on $b$ is not required.'
author:
- 'Nai-Hui Chia[^1]'
- 'Han-Hsuan Lin$^{*}$'
- 'Chunhao Wang$^{*}$'
bibliography:
- 'ref.bib'
title: 'Quantum-inspired sublinear classical algorithms for solving low-rank linear systems'
---

Acknowledgements
================

We thank Scott Aaronson for the valuable feedback on a draft of this paper. We also thank Tongyang Li for pointing out reference @AKP18.

[^1]: University of Texas at Austin, Department of Computer Science.

{'source': 'arXiv_out/1811'}