Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice

Pedro C. S. Costa, Alexander M. Dalzell, Dong An, Dominic W. Berry (Apr 27 2026).

Abstract: Optimal quantum linear equation solvers provide complexity $O(\kappa\log(1/\epsilon))$, where $\kappa$ is the condition number and $\epsilon$ is the allowable error. The optimal solver using a discrete adiabatic approach [PRX Quantum \textbf3, 040303 (2022)] has large analytically proven constant factors for the upper bound on the complexity. The constant factors were later found to be about 1,200 times smaller in numerical testing [Quantum \textbf9, 1887 (2025)]. This meant it is about an order of magnitude more efficient than using a randomised approach from [PRX Quantum \textbf6, 040373 (2025)], which has far smaller analytically proven constant factors. Recently, a ``Shortcut'' method has been found to provide an optimal solver which also has small proven constant factors. In the present work, we conduct a comprehensive numerical analysis comparing this method with the adiabatic solver for two families of random linear systems. We find that, in the case where the solution norm is \emphunknown, the adiabatic solver provides slightly better performance. If the solution norm is \emphknown, then the shortcut method provides significantly better performance for non-Hermitian matrices.

Arxiv: https://arxiv.org/abs/2604.22185