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

Abstract

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. [Subaşi 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 $\hat{I}º$ of the linear system and the target error $\hat{I}\mu$. 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(\hat{I}º\log (1/\hat{I}\mu ))$ -- an exponential improvement in $\hat{I}\mu$, and a shaving of a $\log \hat{I}º$ scaling factor in $\hat{I}º$. 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\hat{I}º$ at $\hat{I}\mu =10^{-10}$ for Hermitian matrices.

19 pages. Published version