An improved quantum-inspired algorithm for linear regression
An improved quantum-inspired algorithm for linear regression
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 [Wossnig, Zhao, and Prakash, Physical Review Letters'18], when the input matrix <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>A</mml:mi></mml:math> is stored in a data structure applicable for QRAM-based state preparation.Namely, suppose …