量子算法实现更高效矩阵乘法,突破经典极限。
Reducing the Complexity of Matrix Multiplication by Quantum Computing
- 基于量子核的算法,门复杂度降为O(N²log₂N)。
- 在模拟与真实量子处理器上验证了精度与资源效率。
- 适合需全程相干计算的深度神经网络推理场景。
矩阵乘法是计算密集型任务的基础操作,也是现代量子加速框架的核心。本文提出一种基于量子核的量子矩阵乘法算法(QKMM),在显式包含振幅编码开销且不依赖QRAM预言机的前提下,实现基本门复杂度O(N²log₂N),显著低于现有最优经典算法的O(N^{2.371339})。在此基础上,构建了一套量子线性代数算子族,涵盖量子向量内积(V²V)、量子向量-矩阵乘法(V²M)、QKMM(M²M)、量子一对多矩阵乘法(O²M)和量子顺序矩阵乘法(SMM),形成从向量到并行与串行矩阵变换的统一框架。通过无噪声模拟、真实噪声建模及超导量子处理器实验,系统评估了该算子框架的数值精度、资源需求与硬件执行极限。进一步将SMM集成至深度神经网络推理中,实现层间特征的相干传播,避免重复测量与重编码。这些成果建立了从量子电路算法设计到端到端相干计算的路径,为以矩阵为中心的计算密集型应用提供了量子计算框架。
原文摘要 · Abstract (English)
Matrix multiplication is a fundamental operation in compute-intensive tasks and a key component of modern quantum acceleration frameworks. Here we present a quantum matrix multiplication algorithm based on quantum kernels (QKMM), achieving an elementary gate complexity of \(O(N^2\log_2N)\), with amplitude encoding overhead explicitly included and without assuming a QRAM oracle. This scaling is asymptotically lower than that of the best-known classical matrix multiplication algorithm \(O(N^{2.371339})\). Building upon QKMM, we establish a family of quantum linear algebra operators, including Quantum Vector Inner Product (V${\scriptstyle 2}$V), Quantum Vector-Matrix Multiplication (V${\scriptstyle 2}$M), QKMM (M${\scriptstyle 2}$M), Quantum One-to-Many Matrix Multiplication(O${\scriptstyle 2}$M) and Quantum Sequential Matrix Multiplication (SMM), providing a unified framework from vector operations to parallel and sequential matrix transformations. Through noiseless simulations, realistic noise modelling and experiments on a superconducting quantum processor, we systematically characterize the numerical accuracy, resource requirements and hardware execution limits of this operator framework. Furthermore, we integrate SMM into deep neural-network inference, enabling intermediate features to propagate coherently across layers without repeated measurement and re-encoding. These results establish a pathway from quantum circuit-level algorithm design to end-to-end coherent computation, providing a quantum computing framework for matrix-centric compute-intensive applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。