Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers

Abstract:Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in many potential quantum computing applications, including machine learning and solving differential equations. The performance of quantum algorithms is often measured by their query complexity, which quantifies the number of oracle calls required to access the input. The main parameters determining the complexity of QLS solvers are the condition number $\kappa$ and sparsity $s$ of the linear system, and the target error $\epsilon$. To date, the best known query-complexity lower bound is $\Omega(\kappa\log(1/\epsilon))$, which establishes the optimality of the most recent QLS solvers. The original proof of this lower bound is attributed to Harrow and Kothari, but their result is unpublished. Furthermore, when discussing a more general lower bound including the sparsity $s$ of the linear system, it has become folklore that it should read as $\Omega( \kappa \sqrt{s}\log(1/\epsilon))$. In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of $\Omega(\kappa\sqrt{s})$ for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters $\kappa,s,\epsilon$ remains an open problem, our result provides a crucial stepping stone toward the complete characterization of QLS complexity.

arXiv:2601.16697 [quant-ph]

(or arXiv:2601.16697v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2601.16697 Focus to learn more arXiv-issued DOI via DataCite

Quantum Sci. Technol. 11 035063 (2026)

https://doi.org/10.1088/2058-9565/ae89e0 Focus to learn more DOI(s) linking to related resources

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.