Before revision: We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [ Chakraborty et al., ICALP'19 ], when the input matrix A is stored in a data structure applicable for QRAM-based state preparation.
After revision: We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [ Chakraborty et al., Physical Review Letters'18 ], when the input matrix A is stored in a data structure applicable for QRAM-based state preparation.