DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.77

Randomized and Quantum Approximate Matrix Multiplication

Authors: Simon Apers, Arjan Cornelissen, and Samson Wang

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

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).

Cite as

Simon Apers, Arjan Cornelissen, and Samson Wang. Randomized and Quantum Approximate Matrix Multiplication. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 77:1-77:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.MFCS.2026.77,
  author =	{Apers, Simon and Cornelissen, Arjan and Wang, Samson},
  title =	{{Randomized and Quantum Approximate Matrix Multiplication}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{77:1--77:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.77},
  URN =		{urn:nbn:de:0030-drops-274591},
  doi =		{10.4230/LIPIcs.MFCS.2026.77},
  annote =	{Keywords: randomized algorithms, quantum algorithms, streaming, approximate matrix multiplication, mean estimation}
}

Search Results

Documents authored by Wang, Samson

Randomized and Quantum Approximate Matrix Multiplication

Abstract

Cite as

Thanks for your feedback!

Could not send message