⚛️ quantum physics

Pauli Decomposition by Character Theory: A Memory-Bounded Algorithm for Qubits and Qudits

本文介绍了一种在 `paulikit` 库中实现的内存受限算法，该算法利用特征理论和快速傅里叶变换（针对量子比特为 Walsh-Hadamard 变换）来高效计算任意算符的泡利分解，而无需对 $2^n \times 2^n$ 稠密矩阵进行实例化。

原作者： Mohammadreza Khellat, Mohammad Masoumi, Saman Nasoori, Soroush Nasoori

发布于 2026-10-07

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Mohammadreza Khellat, Mohammad Masoumi, Saman Nasoori, Soroush Nasoori

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

量子计算机有望解决当今超级计算机需要数千年才能破解的问题，从设计新药到模拟复杂材料。为了实现这一目标，它们必须模拟量子系统的行为，而这些系统受被称为哈密顿量（Hamiltonians）的数学对象支配。这些对象描述了能量如何在系统中移动和变化。然而，量子硬件无法原生理解这些复杂的、连续的描述。相反，工程师必须将它们翻译成机器所使用的特定语言：一种被称为泡利字符串（Pauli strings）的简单、离散的构建模块。这种翻译过程被称为泡利分解（Pauli decomposition），是几乎所有量子算法必不可少的第一步。如果没有它，计算机就无法开始工作。问题在于，对于具有许多部分的系统，这些构建模块的数量会呈指数级爆炸，使得翻译过程变得极其缓慢且耗费内存，以至于在目前的机器上往往无法运行。

Beavernets Technologies 的一个研究小组开发了一种执行这种翻译的新方法，打破了长期阻碍该领域的内存壁垒。他们的工作围绕着一个名为 paulikit 的软件工具展开，该工具允许科学家在无需将整个庞大且笨重的数学对象一次性存储在计算机内存中的情况下，对大规模量子算符进行分解。在传统方法中，计算机必须在开始分解之前，将系统的完整稠密矩阵加载到内存中。对于规模较大的系统，例如拥有 300 个谐振子的系统（对应 16 个量子比特），仅存储保留下来的非零项就需要约 44 GiB 的内存，如果使用完整的稠密矩阵则需要 64 GiB，这已经超出了普通笔记本电脑的承受范围，需要大型内存工作站。新方法通过将问题视为一系列可以逐一处理的小型独立任务，并将结果实时流式传输输出，从而极大地降低了内存需求。对于上述 300 个谐振子的系统，该软件在整个分解过程中的峰值内存占用保持在约 100 MiB 以下。需要注意的是，对于稀疏矩阵输入，paulikit 可以避免构建完整的稠密算符；但如果输入本身已经是稠密的，当前版本的软件仍需在内存中保留该稠密矩阵。这使得研究人员能够处理拥有超过十亿个不同项的系统，这种规模在标准分解技术中是难以实现的。

他们发现的核心在于对这种翻译背后的数学进行了全新的视角审视。研究人员意识到，这个问题可以通过特征理论（character theory）的角度来理解，这是研究群对称性如何相互作用的一个数学分支。通过将量子系统视为一个由位移和符号组成的网格，他们证明了寻找每个构建模块系数的复杂任务，在数学上等同于一种特定类型的快速傅里叶变换（fast Fourier transform）——这是一种用于分析信号的已知算法。这一洞察使他们能够用一种更快速、更具结构化的方法取代缓慢的暴力计算。他们还证明，这种方法不仅适用于标准的量子比特，还能够清晰地扩展到高维系统（即量子比特 qudits），为更先进的量子硬件指明了一条通用的路径。

他们工作的一个关键部分在于澄清了关于如何定义这些构建模块的一个长期存在的歧义。在量子领域，有两种编写同一数学对象的方式：一种版本仅使用实数，而另一种版本则在特定的重叠处插入虚数，以确保这些部分表现得像物理可观测量。研究人员证明，最初的、更简单的版本本身就是一个完整且有效的分解。添加虚数的步骤并非数学本身的强制要求，而是为了确保单个部分可以在真实的设备上用作物理门或测量而做出的选择。通过将数学分解与这种物理约定分离，他们表明复杂的计算可以在更简单的形式下完成，而最后的调整仅在最后阶段应用。这种区分消除了核心算法中不必要的复杂性。

为了证明其方法在现实世界中的有效性，该团队在一个全耦合谐振子网络（fully coupled oscillator network）的模型上进行了测试，该系统模拟了振动如何在质量块和弹簧组成的网络中传播。他们将测试推向了一个包含 300 个谐振子的系统，这相当于一个拥有超过 14 亿个非零项的量子算符。在传统方法下，处理此类规模的系统需要巨大的内存资源，而新方法处理相同的系统时，整个过程的峰值内存占用极低。研究人员通过将结果与独立计算进行对比验证了其准确性，发现数值达到了机器精度的极限，证实了这些节省内存的技巧并未牺牲精度。

该团队还严格分析了其软件在现代多核处理器上的性能。他们发现该算法具有高效的扩展性，能够利用多个处理器核心来加速计算。通过测量每一步实际花费的时间并将其与理论极限进行比较，他们表明该软件受限于数据通过计算机内存传输的速度，而非处理器的原始速度。这意味着在适度的硬件上，运行时间而非内存将成为实际的限制因素。此外，该软件的 API 还支持非厄米算符（non-Hermitian operators）——这类数学对象对于某些高级模拟至关重要。

虽然该软件目前针对标准量子比特进行了优化，但他们开发的数学框架具有足够的通用性，可以应用于量子比特 qudits，这种高维量子单元在未来可能会提供更高效的计算。研究人员指出，虽然系数提取适用于这些系统，但当前量子实验中使用的特定量子纠错和随机化技术并不能自动转移到这些高维领域。这种谨慎的区分确保了用户不会误认为该软件解决了量子比特领域的所有问题，而无需进一步的工作。该团队已将其代码和所有性能测试数据公开发布，以便其他科学家验证结果并在此基础上进行开发。

这项工作的意义不在于它在理论层面上改变了计算的基本速度，而在于它拆除了防止大规模系统进行计算的实际障碍。通过将内存需求与问题规模解耦，研究人员为模拟此前过于庞大而无法进行分解的量子系统打开了大门。这使得物理学家和化学家能够应对更真实的材料和分子模型，从而更接近于量子计算机能够为物理世界提供真实见解的那一天。这篇论文证明了，有时最强大的进步并非来自发明新的物理定律，而是来自找到一种更聪明的方法来组织已有的数据。

技术摘要：基于特征理论的 Pauli 分解

问题陈述
Pauli 分解是包括 Trotter 化、相位估计、稀疏哈密顿量模拟以及变分观测量在内的量子算法的基础前提。该任务涉及将一个任意的 $n$ 位量子比特算符 $H$ 表示为 Pauli 串的线性组合：
$H = \sum_{x,z} c_{x,z} P(x, z)$
其中 $P(x, z)$ 是 $\{I, X, Y, Z\}$ 的张量积。直接通过迹投影（ $c_{x,z} = \text{Tr}(H \cdot P(x,z))/2^n$ ）计算这些系数的方法，其计算成本为 $O(2^{5n})$ 或 $O(2^{3n})$ （取决于具体实现），这使得在大规模系统中变得不可行。虽然先前的研究（例如 Georges 等人，Hamaguchi 等人）已利用快速沃尔什-哈达玛变换（FWHT）将渐近时间复杂度降低至 $O(n \cdot 4^n)$ ，但这些方法通常需要将完整的 $2^n \times 2^n$ 算符矩阵实例化在内存中。这造成了“内存墙”问题，即峰值内存使用量按 $O(4^n)$ 比例缩放，限制了其在实际应用处理大规模系统的能力，即便最终生成的 Pauli 展开是稀疏的。

方法论
本文通过 $(\mathbb{Z}_2)^n$ 阿贝尔群的特征理论（Character Theory） 对 Pauli 分解进行了重新建模。

基于特征理论的推导：
- 作者将对角 Pauli 串（ $Z^{\otimes z}$ ）识别为群 $(\mathbb{Z}_2)^n$ 的特征 $\chi_z(v) = (-1)^{\langle v, z \rangle}$ 。
- 一个通用的 Pauli 串 $X^{\otimes x}Z^{\otimes z}$ 被视为一个位移算符 $X^{\otimes x}$ 与一个特征 $\chi_z$ 的耦合。
- 分解过程被证明等价于执行 $2^n$ 个独立的快速沃尔什-哈达玛变换（FWHT）。对于固定的位移 $x$ ，系数是通过将矩阵元素向量 $\{T_{v, v+x}\}_v$ 对特征进行变换来获得的。
- 论文区分了**“裸”基底**（ $X^{\otimes x}Z^{\otimes z}$ ）与**“真实”基底**（在重叠量子比特处插入 $Y = iXZ$ ）。算法首先在“裸”基底中计算分解（步骤 1），然后应用相位修正 $i^{|x \wedge z|}$ 以转换为“真实”基底（步骤 2）。这种分离表明，两者的计算成本是相同的，且基底的选择是由满足门编译所需的埃尔米特（Hermitian）项这一相位约定驱动的，而非代数上的必然要求。
内存受限的流式实现 (paulikit)：
- 为了克服内存瓶颈，作者实现了一种流式算法。对于稀疏矩阵输入，该算法通过流式处理 $(x, z, \text{coefficient})$ 块，而无需实例化完整的 $2^n \times 2^n$ 稠密算符。
- 块独立性（Chunk Independence）： 利用引理 2，将位移 $x$ 划分为不相交的块。每个块都被独立处理：收集行 $T_{v, v+x}$ ，通过 FWHT 进行变换，进行相位修正并进行阈值处理。
- 流式累积： 算法并不存储稠密的中间数组，而是为每个块生成原始的 $(x, z, \text{coefficient})$ 三元组。这确保了在处理稀疏输入时，峰值内存使用量被限制在 $O(\text{chunk\_size} \times 2^n + N_{\text{terms}})$ ，其中 $N_{\text{terms}}$ 是存活系数的数量，而非整个算符的大小。对于已有的稠密输入（assume_dense=True），虽然每个块的工作集保持较小，但整个进程的内存仍需持有该稠密输入矩阵。
- 优化： 实现过程中使用编译后的 C 内核取代了 Python 层级的循环，以最小化开销。它支持进程池和线程池并行化，并根据是否存在编译内核提供自动选择机制，以避免 GIL 争用。

核心贡献

特征理论公式化： 论文提供了一个明确植根于 $(\mathbb{Z}_2)^n$ 特征理论的 $O(n \cdot 4^n)$ Pauli 分解算法推导，并自然地推广到了通过 $(\mathbb{Z}_p)^n$ 上的离散傅里叶变换进行的量子比特（qudits）分解（推论 1）。
基底澄清： 文中明确展示了在“裸”基底中的分解是完备的，且在计算上等同于“真实”基底，后者仅是一个简单的相位调整。这澄清了使用 $Y$ 是一种为了满足埃尔米特性的约定，而非变换本身的必要条件。
内存受限算法： 主要的工程贡献是 paulikit 库。在处理稀疏输入时，它在实现 $O(n \cdot 4^n)$ 时间复杂度的同时，保持了与完整算符大小无关的峰值内存使用量。这使得分解那些希尔伯特空间维度远超可用 RAM 的算符成为可能。
严格验证与界限： 作者提供了详尽的逐项正确性检查（高达 $1.47 \times 10^9$ 项），并推导了理论上的工作量-跨度（Work-Span）和内存带宽上限。这些界限通过在特定的低端 Linux 平台上进行测量得到了验证。

结果

可扩展性： 算法在全耦合谐振子族（fully coupled oscillator network）上进行了测试。在 $N=150$ 个谐振子（需要 14 个量子比特，希尔伯特空间维度为 $2^{14} = 16,384$ ）的情况下，算符具有 $91,652,096$ 个非零 Pauli 项。
内存效率： 在 $N=150$ 时，朴素的稠密方法仅需数 GiB，在笔记本电脑上即可运行。然而，当规模扩大到 $N=300$ （ $n=16$ ，约 $1.47 \times 10^9$ 项）时，仅存活的三元组就需要约 44 GiB，而完整的稠密矩阵则需 64 GiB。通过测量 $N=50$ 到 $N=300$ 的流式分解过程，发现当项数增长 $1165\times$ 时，paulikit 的分解内存仅从 13.2 MiB 增长到 46.0 MiB，整个进程的峰值 RSS 仅从 64.7 MiB 增长到 99.6 MiB，证实了内存使用与结果大小是解耦的。
性能： 在 4 核平台上，线程化实现实现了 $1.81\times$ （2 个工作者）和 $3.36\times$ （4 个工作者）的加速，紧密符合基于测得串行部分的阿姆达尔定律（Amdahl's law）预测。编译内核达到了 $1.34 $GFLOPs/s 的吞吐量，证实了内核是内存受限的（运行在平台持续带宽上限的$ \sim 34%$）。
正确性： 所有系数均通过独立的投影法进行了验证，最大绝对误差为 $8.7 \times 10^{-19}$ ，与机器精度一致。

意义与主张
论文谦虚地声称，其主要贡献在于内存可扩展性，而非降低渐近时间复杂度（其仍为 $O(n \cdot 4^n)$ ，与之前的最先进技术持平）。其意义在于使大规模、稀疏算符的 Pauli 分解变得可行，而这些算符此前因内存限制而无法处理。

理论范围： 本工作确立了“真实”Pauli 基底是 $(\mathbb{Z}_2)^n \times (\mathbb{Z}_2)^n$ 中心扩张中的一个相位约定，并且特征理论方法可以自然地推广到量子比特（qudits）。
实践范围： paulikit 库能够实现非埃尔米特算符（将其作为一等公民输入）以及大型稀疏哈密顿量的分解，且无需超级计算资源。
局限性： 作者明确指出，虽然系数提取可以提升到量子比特（qudits）层面，但 Clifford 扭转（Clifford twirling）的设计属性（如 2-设计）并不会自动提升到复合维度。论文并未声称解决了量子比特的 Clifford 扭转问题，也没有提供量子比特模块。性能界限是针对所测试的硬件给出的，并未声称在所有机制下都具有普遍优越性。

总之，本文提出了一种具有理论依据且内存高效的 Pauli 分解实现方式，弥合了 $O(n \cdot 4^n)$ 理论复杂度与大规模量子模拟实际约束之间的鸿沟。

技术摘要：基于特征理论的 Pauli 分解

类似论文