# Randomized and quantum approximate matrix multiplication

Preprint · Simon Apers, Arjan Cornelissen, Samson Wang

- Archive id: arxiv:2510.08509
- Published: 2025-10-09
- arXiv: https://arxiv.org/abs/2510.08509
- Source URL: https://arxiv.org/abs/2510.08509
- PDF: https://arxiv.org/pdf/2510.08509
- Provenance: arxiv

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

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.