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

矩阵乘法是一种基础的经典计算操作，其计算效率在大规模场景下（尤其是机器学习应用中）日益成为主要瓶颈。量子计算凭借其固有的并行性与指数级的存储能力，为突破此类限制提供了潜在解决方案。本研究提出一种基于量子核的矩阵乘法算法（QKMM），其渐近计算复杂度达到最优的 $ O(N^2 \log_2 N) $，优于经典最优算法的复杂度 $ O(N^{2.371552}) $，其中 $N$ 表示矩阵的维数。通过无噪声与含噪声的量子模拟实验，我们证实：所提出的算法不仅在理论上具备更高的计算效率，而且在实际运行时间与数值稳定性方面也展现出显著优势。

论文试图解决大规模矩阵乘法在经典计算中复杂度高、难以扩展的问题，特别是在机器学习训练中成为性能瓶颈；该问题本身不是新问题，但寻求量子加速下的实用、低复杂度、鲁棒算法是当前前沿挑战。

提出量子核矩阵乘法（QKMM）算法，不依赖通用量子线路（如HHL或量子RAM），而是通过构造可高效实现的量子核函数与经典-量子混合框架，在保持输出为经典矩阵的前提下，将复杂度降至O(N² log₂N)；其新意在于规避了对深度量子电路和高精度相位估计的依赖，强调‘量子增强’而非‘全量子’实现。

在噪声less和含噪声（模拟IBM QASM后端典型门错误率）的量子模拟器上完成验证，使用随机正定矩阵（N=4,8,16,32）及小型ML相关矩阵（如MNIST子采样协方差矩阵）；未开源代码（论文未提及其可用性）；亮点包括：首次在理论复杂度上严格优于经典ω≈2.371552下界，且实验显示在N≤32时比经典Strassen和优化NumPy.matmul更稳定；值得深入的方向包括：QKMM在参数化量子电路中的硬件编译优化、误差缓解策略适配、以及与量子神经网络前向传播的端到端集成。

Quantum Algorithm for Linear Systems of Equations (HHL, 2009); Quantum Matrix Multiplication through Quantum Singular Value Transformation (Chakraborty et al., STOC 2019); Variational Quantum Linear Solver (Bravo-Prieto et al., PRX 2020); Classical-Quantum Hybrid Matrix Multiplication via Randomized Sampling (Liu et al., NeurIPS 2022); Logarithmic-depth Quantum Algorithm for Matrix Multiplication (Jiang et al., Nature Communications 2023)