Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm
This work presents a significant theoretical advancement for large-scale matrix multiplication, a bottleneck for machine learning applications, by proposing a quantum algorithm with an asymptotically optimal complexity.
This paper introduces a quantum algorithm for matrix multiplication, QKMM, that achieves a computational complexity of $O(N^2 log_2 N)$, which is asymptotically optimal and improves upon the classical optimal complexity of $O(N^{2.371552})$. The algorithm demonstrates superior theoretical efficiency and practical advantages in runtime and stability in quantum simulation experiments.
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.