{"ID":2858326,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.08509","arxiv_id":"2510.08509","title":"Randomized and quantum approximate matrix multiplication","abstract":"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).","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2510.08509","url_pdf":"https://arxiv.org/pdf/2510.08509v1","authors":"[\"Simon Apers\",\"Arjan Cornelissen\",\"Samson Wang\"]","published":"2025-10-09T17:44:03Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\"]","methods":"[]","has_code":false}