{"ID":2881244,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.13108","arxiv_id":"2508.13108","title":"A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems","abstract":"We describe and analyze a simple algorithm for sampling from the solution $\\mathbf{x}^* := \\mathbf{A}^+\\mathbf{b}$ to a linear system $\\mathbf{A}\\mathbf{x} = \\mathbf{b}$. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of $\\mathbf{A}$. Our algorithm produces a compressed representation of some vector $\\mathbf{x}$ for which $\\|\\mathbf{x}^* - \\mathbf{x}\\| \u003c \\varepsilon \\|\\mathbf{x}^* \\|$ in $\\widetilde{O}(κ_{\\mathsf{F}}^4 κ^2 / \\varepsilon^2)$ time, where $κ_{\\mathsf{F}} := \\|\\mathbf{A}\\|_{\\mathsf{F}}\\|\\mathbf{A}^{+}\\|$ and $κ:= \\|\\mathbf{A}\\|\\|\\mathbf{A}^{+}\\|$. The representation of $\\mathbf{x}$ allows us to query entries of $\\mathbf{x}$ in $\\widetilde{O}(κ_{\\mathsf{F}}^2)$ time and sample proportional to the square entries of $\\mathbf{x}$ in $\\widetilde{O}(κ_{\\mathsf{F}}^4 κ^6)$ time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of $\\mathbf{A}$. Our analysis, which is elementary, non-asymptotic, and fully self-contained, simplifies and clarifies several past analyses from literature including [Gilyén, Song, and Tang; 2022, 2023] and [Shao and Montanaro; 2022].","short_abstract":"We describe and analyze a simple algorithm for sampling from the solution $\\mathbf{x}^* := \\mathbf{A}^+\\mathbf{b}$ to a linear system $\\mathbf{A}\\mathbf{x} = \\mathbf{b}$. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of $\\mathbf{A}$. Our algorithm produces a...","url_abs":"https://arxiv.org/abs/2508.13108","url_pdf":"https://arxiv.org/pdf/2508.13108v1","authors":"[\"Tyler Chen\",\"Junhyung Lyle Kim\",\"Archan Ray\",\"Shouvanik Chakrabarti\",\"Dylan Herman\",\"Niraj Kumar\"]","published":"2025-08-18T17:14:35Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"quant-ph\"]","methods":"[]","has_code":false}