The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is TightResearch Paper
Quantum algorithms for linear algebra access a dense matrix through quantum random access memory and prepare a state proportional to the solution of a linear system (Harrow, Hassidim, Lloyd 2009; Kerenidis, Prakash 2017; Gilyén, Su, Low, Wiebe 2019). Their cost depends on the normalized Frobenius norm and the condition number …