量子计算降低矩阵乘法的复杂度

本文基于 Jiaqi Yao, Tianjian Huang, Tonghe Zhang, Ding Liu 等人 2026 年论文《Reducing the Complexity of Matrix Multiplication by Quantum Computing》整理。原稿提出了基于量子核的矩阵乘法算法（QKMM），并围绕其构建了一族量子线性代数算子。本文聚焦于算法的核心思想、算子体系的数学框架与量子线路设计，对实验部分做精简介绍，力求以清晰的中文讲解呈现这一量子加速框架的完整脉络。

1. 引言：矩阵乘法复杂度的五十年追求

1.1 经典矩阵乘法的发展历程

矩阵乘法是计算密集型任务中的基本运算，也是深度学习模型训练的核心。降低矩阵乘法的复杂度一直是理论计算机科学的重要目标。

自 Strassen（1969）突破性地给出 (O(N^{2.81})) 算法以来，一系列里程碑式的成果不断推低复杂度的上界：

Pan（1980）：三线性聚合技术
Coppersmith–Winograd（1982, 1987）：张量积方法，降至 (O(N^{2.495548}))
Le Gall（2014）：增强激光方法，(O(N^{2.3728596}))
AlphaTensor（DeepMind, 2022）：强化学习发现 70 余种新算法；同期不对称哈希方法达到 (O(N^{2.371866}))
Williams et al.（2024）：递归激光方法结合不对称哈希，(O(N^{2.371552}))
Alman et al.（2025）：进一步引入不对称性，当前最优 (O(N^{2.371339}))

五十余年的追求逐步推进了计算复杂度的边界，但也表明经典方法的改进空间日益收窄。

1.2 量子矩阵乘法的现状与挑战

鉴于经典方法的瓶颈，研究者开始借助量子计算的并行性设计更高效的矩阵乘法方法。然而，当前量子矩阵乘法（QMM）研究缺乏统一的评估框架：

有的工作以查询复杂度（query complexity）度量，通常基于预言机（oracle）假设
有的以量子比特数或门复杂度度量
有的以乘法次数度量

早期工作基于模加法器和模乘法器构建通用量子线路，但依赖线路堆叠，导致 (O(N^3)) 的量子资源开销。近期有工作利用 Hadamard 测试设计量子内积算法并推广到矩阵乘法，但经本文完整分析，其基本量子门复杂度为 (O(N^3 \log_2 N))。

2. 振幅编码与量子核方法

2.1 振幅编码

振幅编码（amplitude encoding）是将经典数据映射到量子态振幅上的方法。给定归一化向量 (|a\rangle \in \mathbb{R}^N)，通过幺正变换 (V_a) 将其编码为量子态：

$$
|a\rangle = V_a |0\rangle^{\otimes n},
$$

其中 (n = \lceil \log_2 N \rceil)。振幅编码的优势在于用 (n) 个量子比特即可表示 (N = 2^n) 维向量。

2.2 量子核内积方法

量子核方法（quantum kernel method）的核心思想是：两个向量的内积可以直接通过量子态的振幅提取。

给定两个归一化向量 (\boldsymbol{a}, \boldsymbol{b} \in \mathbb{R}^N)，其振幅编码态分别为 (|\boldsymbol{a}\rangle = V_a|0\rangle^{\otimes n}) 和 (|\boldsymbol{b}\rangle = V_b|0\rangle^{\otimes n})。对 (|\boldsymbol{a}\rangle) 施加 (V_b^{-1}) 后，基态 (|0\rangle^{\otimes n}) 的振幅恰好等于内积：

$$
\langle 0|^{\otimes n} V_b^{-1} V_a |0\rangle^{\otimes n} = \langle \boldsymbol{b} | \boldsymbol{a} \rangle.
$$

因此，测量得到基态的概率为

$$
P(0^{\otimes n}) = |\langle \boldsymbol{b} | \boldsymbol{a} \rangle|^2 / N,
$$

通过重复测量即可估计内积的平方值。

3. 量子线性代数算子族

本文围绕 QKMM 构建了五个层次的量子线性代数算子，从基本的向量运算到复杂的矩阵链式乘法。

3.1 V2V：量子向量内积

V2V（Vector to Vector）是最基本的算子，计算两个高维向量的内积模长。

量子线路的演化过程如下：

初始化：(|\phi_0\rangle = |0\rangle^{\otimes n})
编码 (\boldsymbol{a})：(|\phi_1\rangle = V_a |0\rangle^{\otimes n})
施加 (V_b^{-1})：(|\phi_2\rangle = V_b^{-1} V_a |0\rangle^{\otimes n})
测量基态概率，得到 (|\langle \boldsymbol{a} | \boldsymbol{b} \rangle|^2)

资源消耗：仅需 (2\log_2 N + 1) 个量子比特，(O(N \log_2 N)) 个基本门。

V2V 的优势在于直接将目标内积映射到指定概率分支，避免了辅助量子比特的干涉测量和间接重构过程，因此比 Swap Test 和 Hadamard Test 更稳定、更精确。

3.2 V2M：量子向量-矩阵乘法

V2M（Vector to Matrix）实现向量与矩阵的线性变换 (\boldsymbol{b} = A\boldsymbol{x})，其中矩阵 (A \in \mathbb{R}^{N \times N})，向量 (\boldsymbol{x} \in \mathbb{R}^N)。

逐元素地，(b_i = \langle A_{i\cdot} | \boldsymbol{x} \rangle)，即矩阵第 (i) 行与向量的内积。

核心设计：利用索引寄存器和多受控振幅编码，在单个线路中并行完成所有行的内积计算。

量子线路的演化过程：

初始化：(|\phi_0\rangle = |0\rangle^{\otimes n} |0\rangle^{\otimes n})
创建均匀叠加：

$$
|\phi_1\rangle = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} |i\rangle |0\rangle^{\otimes n}
$$

多受控编码矩阵行与输入向量：

$$
|\phi_2\rangle = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} |i\rangle \otimes V_{\boldsymbol{x}}^{-1} V_{A_i} |0\rangle^{\otimes n}
$$

测量基态 (|i\rangle|0\rangle^{\otimes n}) 的概率正比于 (|b_i|^2 / N)

资源消耗：(2\log_2 N) 个量子比特，(O(N^2 \log_2 N)) 个基本门。

3.3 M2M：量子矩阵乘法（QKMM）

M2M（Matrix to Matrix）是核心算子，计算两个矩阵的乘积 (C = AB)，其中 (A, B \in \mathbb{R}^{N \times N})。

逐元素地，(c_{ij} = \langle A_{i\cdot} | B_{\cdot j} \rangle)，即矩阵 (A) 的第 (i) 行与矩阵 (B) 的第 (j) 列的内积。

核心设计：使用双索引寄存器分别编码矩阵 (A) 的行和矩阵 (B) 的列，通过多受控振幅编码将所有交叉内积整合到单个线路中。

量子线路的演化过程：

初始化三个寄存器：(|\phi_0\rangle = |0\rangle^{\otimes n} |0\rangle^{\otimes n} |0\rangle^{\otimes n})
创建行、列索引的均匀叠加：

$$
|\phi_1\rangle = |0\rangle^{\otimes n} \otimes \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} |i\rangle \otimes \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} |j\rangle
$$

多受控编码：

$$
|\phi_2\rangle = \frac{1}{N} \sum_{j=0}^{N-1} \sum_{i=0}^{N-1} |j\rangle |i\rangle V_{B_j}^{-1} V_{A_i} |0\rangle^{\otimes n}
$$

测量基态 (|j\rangle|i\rangle|0\rangle^{\otimes n}) 的概率正比于 (|c_{ij}|^2 / N^2)

资源消耗：(3\log_2 N) 个量子比特，(O(N^2 \log_2 N)) 个基本门。

这是本文的核心结果：以基本量子门数衡量，QKMM 的门复杂度为

$$
O(N^2 \log_2 N),
$$

渐近地低于当前最优经典矩阵乘法算法的 (O(N^{2.371339}))。

3.4 O2M：一对多矩阵乘法

O2M（One-to-Many Matrix Multiplication）使一个矩阵同时与一组不同的幺正矩阵相乘：

$$
C_i = A \cdot B_i, \qquad i = 0, 1, \ldots, K-1.
$$

这一操作天然对应于 Transformer 网络中的多头注意力机制和并行多任务量子神经网络。

核心设计：引入专用的头索引寄存器（head-index register），在全相干叠加态中定向调度幺正操作 (B_k) 的条件执行。仅需 (\lceil \log_2 N \rceil + \lceil \log_2 K \rceil) 个辅助索引量子比特。

资源消耗：(2\log_2 N + \log_2 K) 个量子比特，(O!\left(N^2 \log_2 N + \sum_{k=0}^{K-1} G_{\text{controlled-}B_k}\right)) 个基本门。

3.5 SMM：顺序矩阵乘法

SMM（Sequential Matrix Multiplication）是架构的顶层算子，执行深层多层网络所需的串行矩阵链乘法：

$$
Y = W^{(L-1)} W^{(L-2)} \cdots W^{(0)} A.
$$

核心设计：采用多阶段受控级联拓扑，利用 Gray 码和动态寄存器交换机制，消除所有中间测量，实现全相干下的无损矩阵链乘法。相比 M2M 仅需额外 (l = \lceil \log_2 L \rceil) 个辅助量子比特。

量子线路的演化过程：

第一层：利用 M2M 算子得到中间矩阵 (Z^{(0)} = W^{(0)} A)
通过数据寄存器基态门控和寄存器交换 (R_a \leftrightarrow R_j)，将前一层特征无缝传递到下一层
经过 (L) 次递归展开后，最终全相干输出态为

$$
|\phi_{\text{out}}\rangle = \frac{1}{N^{(L+1)/2}} \sum_{i,j} |i\rangle|j\rangle \prod_{m=0}^{L-1} V_{W_j^{(m)}}^\dagger V_{A_i} |0\rangle_a |g_{L-1}\rangle_g
$$

其中零态振幅满足

$$
\langle 0|a \prod{m=0}^{L-1} V_{W_j^{(m)}}^\dagger V_{A_i} |0\rangle_a = \left[W^{(L-1)} W^{(L-2)} \cdots W^{(0)} A\right]_{ji}.
$$

资源消耗：(3\log_2 N + \log_2 L) 个量子比特，(O(LN^2 \log_2 N)) 个基本门。

4. 算子族的层次结构

这五个算子构成了一个层次化的量子线性代数框架：

算子	功能	量子比特	门复杂度
V2V	向量内积	(2\log_2 N + 1)	(O(N \log_2 N))
V2M	向量-矩阵乘法	(2\log_2 N)	(O(N^2 \log_2 N))
M2M	矩阵乘法	(3\log_2 N)	(O(N^2 \log_2 N))
O2M	一对多矩阵乘法	(2\log_2 N + \log_2 K)	(O(N^2 \log_2 N + \cdots))
SMM	顺序矩阵乘法	(3\log_2 N + \log_2 L)	(O(LN^2 \log_2 N))

V2V 和 V2M 是基础算子，M2M 构成量子矩阵运算的核心。在 M2M 基础上，O2M 支持并行多分支计算（对应多头注意力），SMM 支持深层网络的链式传播。

5. 测量复杂度分析

量子计算包含两类资源：相干计算资源（线路执行）和测量资源（从量子态提取经典信息）。

QKMM 的输出编码在量子态的振幅中。要获取完整的经典矩阵输出，需要进行多次测量。利用 Hoeffding 不等式等数学工具，可以推导出测量复杂度为

$$
O!\left(\frac{\log_2 N^2 + \log_2(1/\delta)}{e^2}\right),
$$

其中 (e) 为逐元素误差，(\delta) 为置信参数。

因此，包含测量开销在内的总渐近复杂度在 (N) 足够大时（例如 (N \sim 10^9) 量级）仍然低于最优经典矩阵乘法算法。

需要强调的是，在端到端量子神经网络推理中，中间结果可以保持相干编码并直接传播到后续操作，无需逐层测量和重新编码。因此，测量开销主要适用于需要完整经典输出的场景。

6. 实验验证

6.1 无噪声仿真

在无噪声理想仿真中，每个算子评估 100 个随机生成的实例。结果表明：

V2V：中位相对误差在 (10^{-2}) 量级，误差分布比 Swap Test 和 Hadamard Test 更集中
V2M：误差随维度增长但始终低于 Hadamard Test
M2M：输出空间随维度二次扩展，在 (N = 64) 时误差达到 (10^{-1}) 量级
O2M：误差随并行矩阵数增加而增长
SMM：累积误差随级联深度 (L) 增加

量子振幅提取与经典基准值的比较显示，两者吻合度接近机器精度，表明 QKMM 线路演化本身在无噪声条件下引入的数值偏差可忽略不计。

6.2 有噪声仿真

基于 IBM Heron 超导量子处理器的校准参数构建噪声模型，包含 (T_1) 弛豫、(T_2) 退相干、单/双量子比特门保真度和读取保真度。

结果揭示了明确的鲁棒性层次：

V2V 对噪声最不敏感（线路浅、受控操作少）
V2M 受受控映射影响逐渐增大
M2M 最脆弱（索引受控操作和双量子比特门最多）

6.3 超导量子计算机实验

在 180 量子比特的本源悟空超导量子计算机上执行 V2V、V2M 和 M2M 线路。线路编译为原生 (R_\phi) 和 CZ 门集。

实验结果与噪声仿真一致：

V2V 在 (N = 2) 时中位相对误差保持 (10^{-2}) 量级，(N = 16) 时达到 (10^{-1}) 量级
V2M 和 M2M 的硬件退化更为显著
验证了当前硬件能够执行基础量子算子，但矩阵级变换对硬件提出了更高要求

7. 量子神经网络推理

7.1 混合框架

将 SMM 嵌入深度学习推理管线，构建经典训练-量子推理混合框架：

在经典计算机上优化模型参数
将固定参数编码到量子线路中
量子推理线路采用 V2M–SMM–M2V 架构：
- V2M 执行初始特征映射
- SMM 通过顺序矩阵乘法在隐藏层间传播中间特征
- M2V 将最终特征表示投影到分类输出

整个推理过程中，中间量子态保持相干传播，仅在最终分类阶段测量。

7.2 实验结果

使用 Iris 数据集构建二特征二分类任务。在 5000 次测量下：

无噪声仿真和 IBM Heron 噪声仿真在所有测试深度下分类准确率均保持 100%
输出误差随隐藏层数增加而增长，但不足以改变最终预测标签
在真实硬件（本源悟空 180）上，中位误差约 0.46，但分类准确率仍为 100%

这表明分类决策对一定程度的数值扰动具有容忍性。

8. 讨论与展望

8.1 QKMM 的定位

QKMM 的价值不在于替代所有经典矩阵运算，而在于提供一条与经典数据交换范式不同的相干计算路径——量子信息可以在其中被持续保持并直接用于后续计算。

与依赖量子随机存取存储器（QRAM）的算法不同，QKMM 不要求 QRAM 作为计算模型的基本假设，而是通过全局量子态编码和相干量子线路实现矩阵变换。

8.2 量子密集计算

本文提出了**"量子密集计算"**（quantum-intensive computing）的概念：利用量子计算资源探索大规模计算主导任务的加速。随着大规模 AI 模型训练和科学计算需求的增长，在计算密集型任务中展示可验证的量子优势，将是推动量子计算从专用算法加速走向更通用计算范式的重要一步。

8.3 未来方向

纠错容错架构下的完整资源分析：当前结果主要基于 NISQ 时代的约束
QRAM 集成：若未来 QRAM 技术成熟，可进一步降低数据加载开销
非线性激活函数的量子实现：当前实验未包含非线性激活，完整深度学习的量子加速需要解决这一问题
更大规模的硬件验证：随着量子比特数和保真度的提升，矩阵级量子计算的可行规模将显著扩大

参考文献

[1] Yao J, Huang T, Zhang T, et al. Reducing the Complexity of Matrix Multiplication by Quantum Computing[J]. arXiv:2602.05541v3 [quant-ph], 2026.

[2] Strassen V. Gaussian elimination is not optimal[J]. Numerische Mathematik, 1969, 13: 354–356.

[3] Alman J, Williams V V. A refined laser method and faster matrix multiplication[C]// TheoretiCS, 2024, 3.

[4] Alman J, et al. More asymmetry yields faster matrix multiplication[C]// SODA 2025: 2005–2039.

[5] Havlíček V, et al. Supervised learning with quantum-enhanced feature spaces[J]. Nature, 2019, 567: 209–212.

[6] Fawzi A, et al. Discovering faster matrix multiplication algorithms with reinforcement learning[J]. Nature, 2022, 610: 47–53.