.png){kind=icon}
.png){kind=icon}
Return
Faster Quantum-inspired Algorithms for Solving Linear Systems
.png){kind=icon}
OA
AI
DOI：10.1145/3520141.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear systemAx = b, we show that there is a classical algorithm that outputs a data structure for x allowing sampling and querying to the entries, where x is such that ||x - A(+) b|| <= is an element of ||A(+) b ||. This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is O-similar to(kappa(6) (F) kappa(2)/C-2), where kappa(F) = ||A || (F) ||A(+) || and kappa = || A || ||A(+) ||. This improves the previous best algorithm [Gilyen, Song and Tang, arXiv:2009.07268] of complexity O(kappa(6) (F) kappa(6/4)). Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution x in time O-similar to(kappa(6) (F)), while the best quantum algorithm known returns | x QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.
Keywords:
Quantum computing
quantum-inspired algorithm
Kaczmarz method
Journal
A
IF:
6.8
Papers:
539
Citations:
508