Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs

Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. [Subacsi et al., Phys. Rev. Lett. (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number kappa of the linear system and the target error ε. Here we go beyond these results in several ways. Firstly, using filtering~[Lin et al., Quantum (2019)] and Poissonization techniques [Cunningham et al., arXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling O(kappa log(1/ε)) -- an exponential improvement in ε, and a shaving of a log kappa scaling factor in kappa. Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation -- which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837 kappa at ε=10-10 for Hermitian matrices.