2025/08/18 by Tyler Chen, Junhyung Lyle Kim, Chen, Tyler +9
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2508.13108
openalex publication_date 2025/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe and analyze a simple algorithm for sampling from the solution x^* := A+b to a linear system Ax = b. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of A. Our algorithm produces a compressed representation of some vector x for which ‖x^* - x‖ < ε ‖x^* ‖ in \widetildeO(κF4 κ2 / ε2) time, where κF := ‖A‖F‖A+‖ and κ:= ‖A‖‖A+‖. The representation of x allows us to query entries of x in \widetildeO(κF2) time and sample proportional to the square entries of x in \widetildeO(κF4 κ6) time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of 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].