Randomized and quantum approximate matrix multiplication

• URL: http://arxiv.org/abs/2510.08509v1
• Date: Thu, 09 Oct 2025 17:44:03 GMT
• Title: Randomized and quantum approximate matrix multiplication
• Authors: Simon Apers, Arjan Cornelissen, Samson Wang,
• Abstract summary: A long line of literature considers randomized algorithms, which return an approximate solution in faster time.<n>We first give refined analyses of classical algorithms based on random walks by Cohen-Lewis (99), and based on sketching by Sarl'os (06) and Drineas-Kannan-Mahoney (06)<n>We then propose an improvement on Cohen-Lewis that yields a single classical algorithm that is faster than all the other approaches.
• Score: 0.718791111462057
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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\'os (`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).

Related papers

• HARLI CQUINN: Higher Adjusted Randomness with Linear In Complexity QUantum INspired Networks for K-Means [0.0]
  We show a quantum performance on and above par with the classical k-means algorithm.<n>We present benchmarks of its accuracy for test cases of both well-known and experimental datasets.
  arXiv  Detail & Related papers  (2025-09-23T02:32:13Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Quantum speedup of leverage score sampling and its application [0.0]
  In this paper, we propose a quantum algorithm to accelerate the computation of leverage scores. As an application, we propose a new quantum algorithm for rigid regression problems with vector solution outputs.
  arXiv  Detail & Related papers  (2023-01-15T14:40:18Z)
• Quantum Algorithm For Estimating Eigenvalue [0.0]
  We provide a quantum algorithm for estimating the largest eigenvalue in magnitude of a given Hermitian matrix. Our quantum procedure can also yield exponential speedup compared to classical algorithms that solve the same problem.
  arXiv  Detail & Related papers  (2022-11-11T13:02:07Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum algorithms for anomaly detection using amplitude estimation [5.20363732303968]
  Anomaly detection algorithm based on density estimation (called ADDE algorithm) is one of widely used algorithms. In this paper, we propose a new quantum ADDE algorithm based on amplitude estimation.
  arXiv  Detail & Related papers  (2021-09-28T15:47:56Z)
• Quantum Inspired Adaptive Boosting [0.0]
  We show that the quantum ensemble method does not have advantage over classical algorithms. We propose methods inspired by combining the quantum ensemble method with adaptive boosting. The algorithms were tested and found to be comparable to the AdaBoost algorithm on publicly available data sets.
  arXiv  Detail & Related papers  (2021-02-01T16:33:14Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.