Metraipolis › archive › dc_1752c276dcaf

A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers — arXiv:2609.22445

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.22445
License (as archived)
CC0-1.0
Archived
2026-10-09T22:46:26.630Z
SHA-256 of the archived text
e6b7a9e49e85337ff9aed7437db5288e372494dcb8f2a61d61b45d50ce49916e
Stable URL of this page
https://metraipolis.com/documento/dc_1752c276dcaf

How to cite

A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers — arXiv:2609.22445 — arXiv (en), https://arxiv.org/abs/2609.22445 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1752c276dcaf (Metraipolis archive dc_1752c276dcaf, sha256 e6b7a9e49e85337ff9aed7437db5288e372494dcb8f2a61d61b45d50ce49916e)
BibTeX
@misc{dc1752c276dcaf,
  title = {A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers — arXiv:2609.22445},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.22445},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1752c276dcaf; sha256 e6b7a9e49e85337ff9aed7437db5288e372494dcb8f2a61d61b45d50ce49916e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.22445. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Quantum linear system solvers form one of the central algorithmic primitives in quantum computing, with applications ranging from differential equations and optimization to machine learning. Their cost is commonly measured through query complexity, which counts the number of oracle calls needed to access the input matrix. In the sparse-access model, this complexity is governed by three parameters: the condition number $\kappa$, the sparsity $s$ of the input matrix, and the target precision $\varepsilon$. The dependence on $\kappa$ and $\varepsilon$ is already well understood through the lower bound $\Omega(\kappa\log(1/\varepsilon))$, which matches the best known scaling in these parameters. Once the sparsity $s$ is included, however, the expected lower bound has long been conjectured to be $\Omega(\kappa\sqrt{s}\log(1/\varepsilon))$. Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound $\Omega(\kappa\sqrt{s})$ for constant error $\varepsilon$. In this work, we complete the picture and prove the full joint lower bound $\Omega(\kappa\sqrt{s}\log(1/\varepsilon))$ in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-22 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.22445 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T22:25:52.299Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).