2026-08-21T18:34:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27459 2026-08-21T14:42:40Z ddc:004 open_access

Randomized and Quantum Approximate Matrix Multiplication Apers, Simon Cornelissen, Arjan Wang, Samson randomized algorithms quantum algorithms streaming approximate matrix multiplication mean estimation The complexity of matrix multiplication is a central topic in computer science. While the focus has traditionally been on exact algorithms, a long line of literature also considers randomized algorithms, which return an approximate solution in faster time. In this work, we adopt a unifying perspective that frames these randomized algorithms in terms of mean estimation. Using it, we first give refined analyses of classical algorithms based on random walks by Cohen-Lewis (`99), and based on sketching by Sarlós (`06) and Drineas-Kannan-Mahoney (`06). We then propose an improvement on Cohen-Lewis that yields a single classical algorithm that is faster than all the other approaches, if we assume no use of (exact) fast matrix multiplication as a subroutine. Second, we demonstrate a quantum speedup on top of these algorithms by using the recent quantum multivariate mean estimation algorithm by Cornelissen-Hamoudi-Jerbi (`22). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Simon Apers and Arjan Cornelissen and Samson Wang 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.77 urn:nbn:de:0030-drops-274591 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.77 eng https://creativecommons.org/licenses/by/4.0/legalcode