Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm

• URL: http://arxiv.org/abs/2602.05541v2
• Date: Mon, 09 Feb 2026 15:03:31 GMT
• Title: Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm
• Authors: Jiaqi Yao, Ding Liu,
• Abstract summary: This work presents a quantum kernel-based matrix multiplication algorithm (QKMM)<n>It achieves anally optimal computational complexity of $ O(N2 log N) $, outperforming the classical optimal complexity of $ O(N2.371552) $.
• Score: 3.5649163180026484
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matrix multiplication is a fundamental classical computing operation whose efficiency becomes a major challenge at scale, especially for machine learning applications. Quantum computing, with its inherent parallelism and exponential storage capacity, offers a potential solution to these limitations. This work presents a quantum kernel-based matrix multiplication algorithm (QKMM) that achieves an asymptotically optimal computational complexity of $ O(N^2 \log_2 N) $, outperforming the classical optimal complexity of $ O(N^{2.371552}) $, where $N$ denotes the matrix dimension. Through noiseless and noisy quantum simulation experiments, we demonstrate that the proposed algorithm not only exhibits superior theoretical efficiency but also shows practical advantages in runtime performance and stability.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Amplitude-Phase Separation toward Optimal and Fast-Forwardable Simulation of Non-Unitary Dynamics [39.740772144144366]
  Amplitude-Phase Separation (APS) methods formulates any non-unitary evolution into separate simulation of a unitary operator and a Hermitian operator.<n>APS provides an effective and generic pathway for developing efficient quantum algorithms for general non-unitary dynamics.
  arXiv  Detail & Related papers  (2026-02-10T09:23:55Z)
• Optimal Scaling Quantum Interior Point Method for Linear Optimization [0.0]
  We introduce a novel almost-exact quantum IPM, where the system is constructed and solved on a quantum computer.<n>This framework achieves an optimal worst-case scaling of $mathcalO(n2)$ for fully dense LO problems.<n>Our algorithm has a quantum complexity of $mathcalO(n1.5 _A log1)$ queries to QRAM and $mathcalO(n2 log(frac1)$ classical arithmetic operations.
  arXiv  Detail & Related papers  (2025-12-04T06:44:22Z)
• Towards efficient quantum algorithms for diffusion probabilistic models [27.433686030846072]
  Diffusion model (DPM) is renowned for its ability to produce high-quality outputs in tasks such as image and audio generation.<n>We introduce efficient quantum algorithms for implementing DPMs through various quantum solvers.
  arXiv  Detail & Related papers  (2025-02-20T04:39:09Z)
• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  We introduce the concept of textitsemi-symmetries in QUBO matrices.<n>We show that our algorithm reduces the number of couplings and circuit depth by up to $45%.
  arXiv  Detail & Related papers  (2024-12-18T12:05:18Z)
• A probabilistic imaginary-time evolution quantum algorithm for advection-diffusion equation: Explicit gate-level implementation and comparisons to quantum linear system algorithms [0.0]
  We propose a quantum algorithm for solving the advection-diffusion-reaction equation.<n>Our algorithm achieves an exponential speedup regarding the matrix size at the cost of a worse dependence on the error bound.
  arXiv  Detail & Related papers  (2024-09-27T08:56:21Z)
• Quantum-Trajectory-Inspired Lindbladian Simulation [16.17464946935405]
  We propose two quantum algorithms for simulating the dynamics of open quantum systems governed by Lindbladians.<n>The first algorithm achieves a gate complexity independent of the number of jump operators, $m$, marking a significant improvement in efficiency.<n>The second algorithm achieves near-optimal dependence on the evolution time $t$ and precision $epsilon$ and introduces only an additional $tildeO(m)$ factor.
  arXiv  Detail & Related papers  (2024-08-20T03:08:27Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Compact quantum algorithms for time-dependent differential equations [0.0]
  We build on an idea based on linear combination of unitaries to simulate non-unitary, non-Hermitian quantum systems.<n>We generate hybrid quantum-classical algorithms that efficiently perform matrix-vector multiplication and matrix inversion operations.
  arXiv  Detail & Related papers  (2024-05-16T02:14:58Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
  We study problems involving the solution of matrix equations, for which there currently exists no efficient, general quantum procedure. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware.
  arXiv  Detail & Related papers  (2021-12-05T15:42:32Z)
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
  Main algorithm is assembled from two components which may be of independent interest. A variant of LINEARSEQ is shown to have adaptive complexity of $O(log(n))$ smaller than that of any previous algorithm in the literature.
  arXiv  Detail & Related papers  (2021-11-15T17:10:40Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)

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.