⚛️ quantum physics

Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth

本文介绍了“双塔矩阵乘法”（Two-Tower Matrix Multiplication），这是一种量子子程序，通过在两个交错层之间进行并行执行并增加比特数需求，将 $K$ 个矩阵链的乘积编码进一个量子态中，且其电路深度与 $K$ 无关（在矩阵维度上实现了多项式对数级的深度）。

原作者： Giacomo Antonioli, Anna Bernasconi, Alessandro Berti, Gianna M. Del Corso, Alessandro Poggiali

发布于 2026-07-16

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Giacomo Antonioli, Anna Bernasconi, Alessandro Berti, Gianna M. Del Corso, Alessandro Poggiali

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个这样的世界：计算机不再仅仅是一个接一个地处理数字，而是与概率共舞，同时探索许多条路径。这就是量子计算的领域，它承诺解决那些当今超级计算机也无法处理的庞大问题。在许多科学挑战的核心——从预测病毒如何传播到训练人工智能——都有一个被称为**矩阵链乘法（matrix chain multiplication）**的任务。把矩阵想象成巨大的、多维的数字电子表格。当你将它们按长链进行相乘时，你本质上是在对数据进行复杂的变换。在经典世界中，随着链条变得越来越长，这种计算会变得越来越慢，就像试图通过踩在一条漫长且蜿蜒的小径上的每一块石头来横渡河流。科学家们一直以来的目标是找到一种“传送”过河的方法，无论水中有多少块石头，都能瞬间得到结果。

本文介绍了一种巧妙的新型量子技巧，称为双塔矩阵乘法（Two-Tower Matrix Multiplication）。这是一种旨在比以往更快地计算长矩阵链乘积的方法，特别是通过让计算的“深度”（即所需时间）保持较短，即使在链条变长时也是如此。作者是来自比萨大学的研究人员，他们已经证明了该方法适用于任何长度的链，并使用真实的量子软件工具构建了其工作版本。虽然它并不能解决所有问题（它仍然需要大量的“内存”，即量子比特），但它提供了一个迷人的权衡：你使用更多的量子内存来节省大量的时间。

问题：长长的电子表格线

想象你是一位正在制作一个巨大、多层三明治的厨师。你有一叠食材：一片面包、一片奶酪、一片火腿、一片面包，等等。为了获得三明治最终的味道，你必须按顺序将它们组合在一起。在数学世界中，这些食材就是矩阵，而将它们结合起来就是乘法。

如果你有一个短的矩阵链，普通计算机可以轻松处理。但如果你有一个长的矩阵链——比如 100 个矩阵——计算机就必须一步步进行数学计算。这就像走过一条长长的走廊，开一扇门，再开下一扇门，然后是下一扇。走廊越长，花费的时间就越多。在经典世界中，所需的时间随矩阵数量线性增长。如果你将链条增加一倍，时间也会增加一倍。

量子计算机则不同。它们使用量子比特（qubits），量子比特可以同时处于多种状态（这是一个被称为“叠加”的概念）。这使得它们能够同时探索许多可能性。然而，构建一个用于进行长矩阵链乘法的量子算法一直很困难。以前的方法就像是在那条长长的走廊上搭建桥梁：要么建造时间太长（电路深度过深），要么需要太多的材料（需要太多量子比特）。

解决方案：双塔技巧

本文的作者提出了一种构建桥梁的新方法，他们称之为**“双塔”（Two-Tower）方法。要理解它，我们可以使用一个传送带工厂**的比喻。

想象你有一条长长的工人队伍（矩阵），他们需要沿着流水线传递一个包裹。

旧方法： 在以前的量子方法中，你可能需要停止流水线，重新组织工人，然后逐个传递包裹。如果有 100 个工人，包裹需要走 100 步才能到达终点。
双塔方法： 作者意识到可以将工人分为两组：“左侧”团队和“右侧”团队。
- 左侧团队（位于位置 0, 2, 4... 的矩阵）同时抓取他们部分的包裹并在同一时刻进行操作。
- 右侧团队（位于位置 1, 3, 5... 的矩阵）也在同一时刻进行操作，但他们做了一件特殊的事情：他们充当一个“筛子”或“过滤器”。

这里的魔力在于：右侧团队使用一种特殊的量子动作（称为伴随态制备/adjoint state preparation），它就像一个神奇的过滤器。它会检查包裹的各个部分是否匹配正确。如果匹配，碎片就会结合并穿过；如果不匹配，它们就会消失进一个不计入结果的“幽灵”状态。因为所有的右侧团队成员都是并行工作的，所以无论线路有多长，整个链条都可以在仅有的两个大步骤内完成处理！

这就是为什么他们称之为“双塔”。电路看起来像是两座上升的操作塔，一座塔处理偶数编号的矩阵，另一座塔处理奇数编号的矩阵。它们在中间汇合，结果便随之产生。

他们的发现与证明

论文提出了几个具体的断言，并得到了数学证明和计算机模拟的支持：

速度与长度无关： 最令人兴奋的发现是，运行此算法所需的时间（电路深度）并不随矩阵数量（ $K$ ）的增加而增长。无论你有 2 个还是 200 个矩阵，计算的“深度”都保持大致不变，仅随单个矩阵的大小（具体而言，是其维度的对数）而变化。这比以往随链条长度增长的方法有了巨大的改进。
权衡关系： 这是一个代价。为了获得这种速度，你需要更多的量子比特（量子内存）。量子比特的数量随链条长度（ $K$ ）线性增长。作者将其描述为“用量子比特换取深度”。你使用更多的内存来节省时间。
适用于任何链： 作者提供了严密的数学证明，表明该方法适用于任何长度的链，无论矩阵数量是奇数还是偶数。他们甚至处理了链条中最后一个元素只是单个向量（一列数字）而非完整矩阵的复杂情况。
现实世界测试： 他们不仅仅是在纸面上做数学题。他们使用两个流行的量子软件框架 Qiskit 和 QCLAB 构建了该算法，并进行了模拟。这些模拟证实了该算法在各种测试用例中都能正确产生预期结果。

“信号”问题

论文还讨论了一个微妙的细节：“信号权重”（signal weight）。在量子力学中，当你运行一个算法时，你通常会得到“正确答案”与一些“噪声”或“幽灵答案”的混合物。“信号权重”是一个衡量最终结果中正确答案相对于噪声占比的度量。

作者发现，对于非常长的“表现良好”的矩阵链（即数字大小大致相同的矩阵），信号权重可能会变得非常小。这就像是在嘈杂的房间里试图听清一声低语：正确答案确实在那里，但它很微弱。然而，他们指出，有一种已知的量子技术叫做振幅放大（Amplitude Amplification），可以增强这种信号，让正确答案变得更响亮，尽管这需要重复执行过程。对于具有“峰值”结构的矩阵（即其中一个数字占主导地位），信号会自然保持强劲。

为什么这很重要

这篇论文并不声称解决了宇宙中的所有问题。它并没有说这种方法能立即治愈疾病或制造时光机。相反，它为需要进行长矩阵链乘法的科学家提供了一个强大的新工具。

这对于以下领域非常有用：

图分析（Graph Analysis）： 理解信息如何在庞大的网络（如社交媒体或互联网）中流动。
机器学习（Machine Learning）： 加速复杂人工智能模型的训练。
求解方程（Solving Equations）： 帮助求解那些对于经典计算机来说过于庞大的线性方程组。

作者谨慎地指出，这是一个子程序（subroutine）——一个构建模块。它是一个专门设计的工具，旨在被插入到更大的量子算法中。虽然该方法需要大量的量子比特（目前这些资源非常稀缺且难以构建），但其能够在计算时间不随链条长度增长的情况下执行这些计算，这在理论和实践上都是向前迈出的重要一步。

简而言之，双塔方法就像是发现了摩天大楼里的秘密电梯。你仍然需要携带行李（量子比特），但你不再需要爬完每一层楼梯（时间），无论大楼有多高，你都可以直接直达顶层。这是发现的一种巧妙、经过证明且经过测试的方法，可以让量子计算机在处理其最重要的任务之一时变得更快。

技术摘要：双塔量子矩阵链乘法

问题陈述
矩阵链乘法定义为计算 $W = M^{(0)} \cdots M^{(K-1)}$ ，其中 $M^{(k)} \in \mathbb{R}^{P_k \times P_{k+1}}$ 。这是科学计算、机器学习和图分析中的一项基础运算。在经典计算中，计算 $K$ 个不同矩阵的乘积需要 $O(KN^\omega)$ 次算术运算（其中 $\omega < 2.372$ ），且即使在无限制并行的情况下，电路深度也会随 $O(\log K \cdot \log N)$ 增长。

在量子领域，现有的线性代数子程序通常依赖于块编码（block-encoding），即将矩阵嵌入为一个幺正矩阵的子块。对于由不同矩阵组成的链，块编码方法通常会导致电路深度随 $K$ 线性增长（ $O(K \cdot \text{polylog}(N))$ ），且辅助量子比特（ancilla qubit）的数量也会随 $K$ 增加。此外，块编码方法的整体亚归一化因子（subnormalization factor）是单个因子的乘积（ $\prod \alpha_k$ ），这可能导致随着 $K$ 的增加，成功概率呈指数级下降。虽然量子奇异值变换（QSVT）为单个矩阵的幂（ $A^K$ ）提供了加速，但目前已知的方法在处理不同矩阵链时，尚无法实现类似的深度无关加速。

方法论：双塔构造
作者提出了“双塔矩阵乘法”（Two-Tower Matrix Multiplication），这是一种将乘积 $W$ 编码进量子态振幅的量子子程序。该构造基于两个主要见解：

状态准备即向量化： 将矩阵条目编码为振幅等同于行向量化。
克罗内克积恒等式： 乘积 $AXB $的向量化满足$ \text{vec}(AXB) = (B^T \otimes A)\text{vec}(X)$。

该算法通过在两个并行层中交错状态准备算子，将两个矩阵乘法子程序（源自 Bernasconi 等人 [15]）推广到任意链长 $K$ ，从而避免了寄存器交换和顺序依赖。

寄存器分配： 电路使用 $K+1$ 个寄存器。对于矩阵链 $M^{(0)}, \dots, M^{(K-1)}$ ，寄存器被分配用于持有行索引和列索引。相邻矩阵共享寄存器，这意味着总量子比特数为 $\Theta(\sum_{k=0}^K \log P_k)$ 。
两层结构：
- 第 1 层 (OP(L))： 对所有偶数索引矩阵（ $M^{(0)}, M^{(2)}, \dots$ ）应用状态准备算子 $SP(M^{(k)})$ 。这些算子作用于不相交的寄存器对，并并行执行。
- 第 2 层 (OP(R))： 对所有奇数索引矩阵（ $M^{(1)}, M^{(3)}, \dots$ ）应用伴随算子 $SP(M^{(k)})^\dagger$ 。这些算子同样作用于不相交的对（具体为偶数索引寄存器之间的共享边界），并并行执行。
- $K$ 为偶数的特殊情况： 如果 $K$ 是偶数，则最后一个矩阵 $M^{(K-1)}$ 没有右邻居。此时，算法使用**模态状态准备（Modular State-Preparation, MSP）**算子代替 $SP^\dagger$ 。该算子将共享索引收缩至 $|0\rangle$ ，同时保留输出列寄存器，否则该寄存器将会丢失。
收缩机制： 核心机制在于以下性质： $SP(M)^\dagger |i, j\rangle$ 将状态投影到 $|0, 0\rangle$ ，其振幅与矩阵条目成正比。通过在共享寄存器上对一个矩阵应用 $SP $并对与其相邻的另一个矩阵应用$ SP^\dagger$，电路通过量子叠加实现对所有共享索引（内积）的求和，从而有效地执行矩阵乘法。

关键结果与复杂度

电路深度： 总电路深度为 $O(\max_k \text{polylog}(P_k P_{k+1}))$ 。至关重要的是，该深度与链长 $K$ 无关。这假设每个矩阵 $M^{(k)}$ 都能在多项式对数时间内被加载到量子态中（例如通过 QRAM）。
量子比特数： 算法需要 $O(\sum_{k=0}^K \log P_k)$ 个量子比特。对于 $K$ 个 $N \times N$ 的方阵，这为 $\Theta(K \log N)$ 。这相对于经典内存（ $O(KN^2)$ ）实现了指数级的压缩，但并非完全脱离 $K$ ——该算法是用量子比特数量换取电路深度。
门计数： 总门计数仍与 $K$ 成线性关系，具体为 $\Theta(K \cdot \text{polylog}(N))$ ，因为总共应用了 $K$ 个状态准备算子。
信号权重 ( $\Omega_W$ )： 输出态包含所需的乘积 $W$ $W$ ，其缩放因子为 $N = 1/\prod \|M^{(k)}\|_F$ $N = 1/ \prod ∥ M^{(k)} ∥_{F}$ 。信号权重定义为 $\Omega_W = \|W\|_F^2 / \prod \|M^{(k)}\|_F^2$ $Ω_{W} = ∥ W ∥_{F}^{2} / \prod ∥ M^{(k)} ∥_{F}^{2}$ 。
- $\Omega_W \leq 1$ 。
- 对于良态矩阵（谱分布平坦）， $\Omega_W$ 随 $K$ 指数级衰减。
- 对于具有尖锐谱结构的矩阵（接近秩-1）， $\Omega_W$ 保持接近 1。
- 作者指出，振幅放大（Amplitude Amplification）可以将 $\Omega_W$ 提升至常数，但代价是需要 $O(1/\sqrt{\Omega_W})$ 次重复，这重新引入了对 $K$ 的依赖。

贡献

深度无关的子程序： 一种用于矩阵链乘法的量子子程序，其电路深度与 $K$ 无关，优于以往所有深度随 $K$ 增长的方法。
正确性证明： 针对任意链长 $K$ （包括奇数和偶数）的正确性形式化证明。
链-向量特化： 用于计算 $Wv$（矩阵链作用于向量）的特化版本，这在迭代求解器和幂法中非常重要。
开源实现： 在 Qiskit 和 QCLAB 框架中的公开实现。

意义与主张
论文将双塔算法定位为作用于矩阵编码态的下游量子算法的高效构建模块。作者明确指出，当下游计算仅需要聚合量（如通过振幅估计可提取的范数、迹、内积或谱性质）而非矩阵条目的完整层析（tomography）时，该优势才会体现。

确定的具体应用包括：

范数估计与方差估计。
图谱分析（计算 $A^K$ 以进行行走计数或混合时间估计）。
求解具有链式结构算子的线性方程组（通过 HHL 或 Neumann 级数 LCU）。
量子机器学习核函数评估。
迭代数值方法（如幂法、Krylov 子空间构建）。

作者对信号权重问题持谨慎态度，承认虽然深度与 $K$ 无关，但信号权重可能会衰减，从而需要振幅放大，这会引入 $K$ 相关的成本。他们并未声称对所有矩阵链任务都具有普遍的指数级加速，而是强调了一个特定的权衡：用量子资源（随 $K$ 线性增长）换取电路深度（常数级）。

未来工作
论文确定了三个研究方向：

混合策略： 在双塔法（常数深度，增长的量子比特）与块编码（增长的深度，较少的量子比特）之间交替使用，以管理信号权重的衰减。
复数矩阵： 将构造扩展到复值矩阵。
幺正链： 将该方法推广到用于量子模拟和过程层析的幺正算子链。