2026-07-21T20:03:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13391 2024-03-06T10:51:52Z ddc:004 open_access

Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension Chia, Nai-Hui Gilyén, András Lin, Han-Hsuan Lloyd, Seth Tang, Ewin Wang, Chunhao sublinear algorithms quantum-inspired regression importance sampling quantum machine learning We present two efficient classical analogues of the quantum matrix inversion algorithm [Harrow et al., 2009] for low-rank matrices. Inspired by recent work of Tang [Tang, 2019], assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix allowing us to sample from the solution to the problem Ax = b using fast sampling techniques. We construct implicit descriptions of the pseudo-inverse by finding approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, our approaches can also be used to apply any desired "smooth" function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem [András Gilyén et al., 2019], our results indicate that more low-rank quantum algorithms can be effectively "dequantised" into classical length-square sampling algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nai-Hui Chia and András Gilyén and Han-Hsuan Lin and Seth Lloyd and Ewin Tang and Chunhao Wang 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.47 urn:nbn:de:0030-drops-133916 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.47 eng https://creativecommons.org/licenses/by/3.0/legalcode