{"id":"arxiv/2601.16697","url":"https://arxiv.org/abs/2601.16697","tags":["quant-ph"],"score":0,"title":"Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers","domain":"quant-ph","source":"arxiv","authors":["Hitomi Mori","Yuta Kikuchi","Marcello Benedetti","Matthias Rosenkranz"],"reviews":0,"subject":"quant-ph","summary":"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 $κ$ and sparsity $s$ of the linear system, and the target error $ε$. To date, the best known query-complexity lower bound is $Ω(κ\\log(1/ε))$, which…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-01-23","reactions":{}}