Universal Matrix Multiplication on Quantum Computer
This addresses the high computational cost of matrix multiplication for machine learning practitioners, but it appears incremental as it builds on existing quantum and classical techniques without demonstrating broad SOTA impact.
The paper tackles the computational bottleneck of matrix multiplication in machine learning by introducing a universal quantum matrix multiplication approach using optimized quantum adders and multipliers based on Quantum Fourier Transform, which reduces gate counts compared to classical methods and extends to the Strassen algorithm, though no concrete performance numbers are provided.
As a core underlying operation in pattern recognition and machine learning, matrix multiplication plays a crucial role in modern machine learning models and constitutes a major contributor to computational expenditure. Hence, researchers have spent decades continuously searching for more efficient matrix multiplication algorithms.This paper firstly introduces an innovative and practical approach to universal quantum matrix multiplication. We designed optimized quantum adders and multipliers based on Quantum Fourier Transform (QFT), which significantly reduced the number of gates used compared to classical adders and multipliers. Subsequently, we construct the basic universal quantum matrix multiplication and extend it to the Strassen algorithm. We conduct comparative experiments to analyze the performance of the quantum matrix multiplication and evaluate the acceleration provided by the optimized quantum adder and multiplier. Finally, we investigate the advantages of the quantum Strassen algorithm and the basic quantum matrix multiplication. Our result opens, for the first time, a reliable pathway for designing universal quantum matrix multiplication. Following this pathway, quantum computing will unlock significantly greater potential for training modern machine learning models.