The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver

Abstract

The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number $\kappa$ and the allowable error $\epsilon$ [PRX Quantum \textbf{3}, 040303 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,200 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is about an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient.

16 pages, 35 figures

References in corpus (8)

• Quantum algorithm for solving linear systems of equations
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Bounds for the adiabatic approximation with applications to quantum computation
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Doubling Efficiency of Hamiltonian Simulation via Generalized Quantum Signal Processing

Cited by in corpus (4)

• Quantum linear system algorithm with optimal queries to initial state preparation
• Block encoding the 3D heterogeneous Poisson equation with application to fracture flow
• Probabilistic quantum algorithm for Lyapunov equations and matrix inversion
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs