Description
Quantum linear system solvers are a central primitive in quantum algorithms, with applications ranging from differential equations to optimization, machine learning, and scientific computing. Several recent algorithms achieve the same optimal asymptotic query complexity, scaling as $O(\kappa \log(1/\epsilon))$, where $\kappa$ is the condition number and $\epsilon$ is the target precision. However, asymptotic scaling alone does not determine practical performance. Constant factors, implementation assumptions, post-processing costs, and available problem information can significantly affect which solver is preferable.
In this work, we provide a detailed numerical constant-factor analysis of two optimal quantum linear system solvers: the discrete-adiabatic quantum-walk method and the recently proposed Shortcut method. We benchmark both approaches on random linear systems, including non-Hermitian, positive-definite, dense, and sparse instances, and compare their performance across condition numbers and target precisions. A central distinction is between the idealized case in which the norm of the solution is known and the more practical case in which this norm is unknown and must be handled by the algorithm.
A key component of our comparison is the inclusion of the filtering stage required to reduce the state-preparation error to the final target solution error. We compare the kernel-projection filtering procedure used in the Shortcut method with the filtering procedure used in the quantum-walk approach, applying a consistent filtering-cost convention when estimating total complexity. This gives a fairer comparison and shows that the filtering analysis can improve effective cost estimates for the Shortcut method.
Our results show that the practical advantage is regime-dependent. In the idealized known-norm setting, the Shortcut method can achieve lower costs, particularly for non-Hermitian systems. In the realistic unknown-norm setting, however, the discrete-adiabatic quantum-walk solver gives the lower overall cost. These findings demonstrate that constant-factor analysis and realistic algorithmic assumptions are essential for assessing optimal quantum linear system solvers beyond big-O scaling.
| I am the presenting author | Yes |
|---|