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. Subaşı . [Phys. Rev. Lett. 122, 060504 (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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"> <a:mi>κ</a:mi> </a:math> of the linear system and the target error <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" display="inline"> <c:mi>ϵ</c:mi> </c:math> . Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"> <e:mi>O</e:mi> <e:mo stretchy="false">(</e:mo> <e:mi>κ</e:mi> <e:mi>log</e:mi> <e:mo></e:mo> <e:mo stretchy="false">(</e:mo> <e:mn>1</e:mn> <e:mo>/</e:mo> <e:mi>ϵ</e:mi> <e:mo stretchy="false">)</e:mo> <e:mo stretchy="false">)</e:mo> </e:math> —an exponential improvement in <k:math xmlns:k="http://www.w3.org/1998/Math/MathML" display="inline"> <k:mi>ϵ</k:mi> </k:math> , and a shaving of a <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline"> <m:mi>log</m:mi> <m:mo></m:mo> <m:mi>κ</m:mi> </m:math> scaling factor in <o:math xmlns:o="http://www.w3.org/1998/Math/MathML" display="inline"> <o:mi>κ</o:mi> </o:math> . 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 <q:math xmlns:q="http://www.w3.org/1998/Math/MathML" display="inline"> <q:mn>837</q:mn> <q:mi>κ</q:mi> </q:math> at <s:math xmlns:s="http://www.w3.org/1998/Math/MathML" display="inline"> <s:mi>ϵ</s:mi> <s:mo>=</s:mo> <s:msup> <s:mn>10</s:mn> <s:mrow> <s:mo>−</s:mo> <s:mn>10</s:mn> </s:mrow> </s:msup> </s:math> for Hermitian matrices.