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 $\kappa$ of the linear system and the target error $\epsilon$. 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/\epsilon ))$ -- an exponential improvement in $\epsilon$, 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 $\epsilon =10^{-10}$ for Hermitian matrices.

19 pages. Published version

References in corpus (25)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Data Fitting
• Bounds for the adiabatic approximation with applications to quantum computation
• Preconditioned quantum linear system algorithm
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Improved quantum algorithms for linear and nonlinear differential equations
• Towards provably efficient quantum algorithms for large-scale machine-learning models
• Block-encoding structured matrices for data input in quantum computing
• Quantum algorithm for time-dependent differential equations using Dyson series
• On efficient quantum block encoding of pseudo-differential operators
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Improved Bounds for Eigenpath Traversal
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Quantum algorithms for computing observables of nonlinear partial differential equations
• Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver