⚛️ quantum physics

An efficient Pauli decomposition algorithm for structured matrices

本文提出了一种随机经典算法，该算法能够在多项式时间内高效地恢复具有承诺稀疏性的结构化矩阵的精确泡利分解，克服了旨在处理通用稠密矩阵的现有方法所存在的指数级复杂度问题。

原作者： Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

发布于 2026-07-01

📖 1 分钟阅读🧠 深度阅读

原作者： Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

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

以下是使用简单语言和日常类比对该论文进行的解释。

核心问题： “泡利谜题” (The Pauli Puzzle)

想象你拥有一本极其庞大且复杂的量子计算机指令手册。这本手册是用一种被称为 泡利字符串 (Pauli strings) 的特殊代码编写的。为了运行量子算法，你需要将这本手册拆解成一个个独立的句子（即泡利字符串），并准确知道每一句在说什么。

然而，对于一个通用的矩阵（即那本指令手册）来说，这个谜题异常困难。这就像试图在一片行星规模的沙滩上寻找一颗特定的沙粒。可能存在的沙粒数量增长得极快（呈指数级增长），以至于即使是最快的超级计算机，处理大型输入所需的时间也会超过宇宙的寿命。

现有的方法试图通过阅读“整片沙滩”来寻找沙粒。它们虽然彻底，但对于我们目前正在构建的量子计算机（称为 NISQ 设备）来说太慢了，根本无法投入实用。

前景：一片“稀疏”的沙滩

这篇论文的作者说：“等等。如果我们面对的不是满是沙子的沙滩呢？如果我们被告知，在整本手册中其实只隐藏着极少数的沙粒呢？”

用技术术语来说，他们假设该矩阵是 稀疏的 (sparse)。这意味着，在数以亿计可能的泡利字符串中，实际上只有极少且可控的数量（我们称之为 $k$ ）正在被使用。

论文提出了这样一个问题：如果我们知道这个谜题很简单（是稀疏的），我们能否在不阅读整片沙滩的情况下快速解决它？

解决方案：一位聪明的侦探

作者创建了一种新的随机算法，其角色就像一位聪明的侦探。这位侦探不会去读手册的每一页，而是利用几个巧妙的技巧来寻找隐藏的沙粒。

以下是这位侦探的工作流程，分为三个步骤：

1. “手电筒”扫描（寻找位置）

想象泡利字符串有两个部分：一个是“位置”部分（动作发生在哪里），另一个是“符号”部分（它是正还是负）。

技巧： 侦探对着手册中的随机行照射手电筒。因为手册是稀疏的，如果某一行确实有内容，侦探可以瞬间识别出哪个“位置”是活跃的。
类比： 这就像走进一个只有几支点燃蜡烛的黑暗房间。你不需要扫描整个房间，只需快速瞥一眼几个点，就能准确知道蜡烛在哪里。算法能非常快速地找到“活跃位置”（称为 唯一的 $x$ 比特串）。

2. “独处”与“拥挤”的房间

一旦侦探找到了一个位置，他们会检查这是一个“独处”的房间还是一个“拥挤”的房间。

独处的房间： 有时，一个位置只有一支蜡烛（一个泡利字符串）。这很简单，侦探只需读出蜡烛上的标签并继续下一步。
拥挤的房间： 有时，多支蜡烛堆叠在同一个位置，它们的灯光可能会相互抵消或混合在一起。这是最难的部分。

3. “折叠”技巧（解决拥挤的房间）

当侦探发现一个拥挤的房间时，他们无法直接读取标签，因为标签已经混杂在一起了。

技巧： 侦探使用了一种叫做 随机折叠 (random folding) 的技术。想象把一张巨大的房间地图折叠进一个小盒子里。
神奇之处： 如果你随机折叠地图，那些“拥挤”的蜡烛很有可能会被分散到盒子的不同角落。突然之间，原本看起来拥挤的角落现在可能只剩下一支蜡烛。
结果： 侦达现在可以读出那支单出的蜡烛。他们从混合物中减去它，然后重复折叠过程，直到找齐拥挤房间里的所有蜡烛。

为什么这很重要

论文证明了这种侦探方法是 高效的。

旧方法： 耗时随指数级增长（例如 $2^{100}$ ）。对于大型问题来说是不可能的。
新方法： 耗时随多项式级增长（例如 $n^3$ ）。这对于实际应用来说足够快。

该算法不仅仅是在猜测；它内置了“认证”步骤。它会自我检查工作，以确保没有出错。如果发现错误，它会报告“失败”并停止，而不是给你一个错误的答案。

总结

论文表明，虽然寻找泡利分解通常是一场噩梦，但如果你预先知道输入是“稀疏的”（即只有少数活跃部分），事情就会变得轻而易举。通过使用随机采样和巧妙的折叠技巧，作者构建了一个能够高效解码这些结构化矩阵的工具，使得将数据加载到近期的量子计算机中变得更加可行。

简而言之： 他们找到了一种解决巨大谜题的方法，其核心在于意识到你不需要看每一块碎片——你只需要随机观察正确的碎片，并将剩下的部分不断折叠，直到它们显露原形。

技术摘要：一种针对结构化矩阵的高效 Pauli 分解算法

问题陈述
将经典的 $2^n \times 2^n$ 矩阵分解为 Pauli 字符串的线性组合，是近程量子算法（特别是化学、机器学习和金融领域）端到端实现中的一个关键瓶颈。许多算法（例如变分量子特征值求解器 VQE 和线性代数求解器）都假设输入数据是以 Pauli 字符串的线性组合（LCU）形式提供的。然而，对于一般的经典指定矩阵，这种分解在先验上是未知的。

现有的针对通用稠密矩阵的算法随量子比特数 $n$ 指数级增长。最直接的方法需要 $O(32^n)$ 的时间，而目前已知的最佳方法（例如在 PennyLane 中）其复杂度为 $O(n4^n)$ 。这种指数级的成本源于在最坏情况下，一个矩阵可能在所有 $4^n$ 个 Pauli 基元素上都有支撑，从而需要恢复所有的系数。

本文解决了一个 承诺版本（promise version） 的 Pauli 分解问题。它假设输入矩阵 $M$ 被保证仅在 $k = \text{poly}(n)$ 个 Pauli 字符串上有支撑。此外，该矩阵通过 经典稀疏查询模型 进行访问，即算法可以检索特定行或列的非零项，而无需在内存中构建完整的 $2^n \times 2^n$ 矩阵。目标是在资源与 $n$ 、 $k$ 以及 $\log(1/\delta)$ 成多项式关系的条件下，以高概率恢复精确的 Pauli 分解（即 Pauli 字符串集合及其系数）。

方法论
作者提出了一种随机化经典算法，利用了承诺的稀疏性（ $k$ ）以及 Pauli 字符串在二进制辛形式（binary symplectic form）下的结构。该算法将问题分解为三个主要阶段：

发现活跃的 Pauli-X 部分 ( $x$ )：
利用引理 1（该引理通过关系式 $x = u \oplus v$ 将行索引 $v$ 、列索引 $u$ 与 Pauli-X 部分 $x$ 联系起来），算法通过查询矩阵的随机行来工作。通过收集非零项的列索引并将其与行索引进行异或运算，算法识别出分解中存在的不同 $x$ 位字符串的集合 $X$ 。这一步依赖于布尔不确定性原理（事实 1）来确保随机查询能以高概率揭示活跃的 $x$ 字符串。
解码唯一的 $x$ 字符串：
对于每个被发现的 $x$ ，算法检查其是否是“唯一的”（即仅与一个 Pauli 字符串相关联，故 $p_x = 1$ ）。如果唯一，查询函数 $b_x(u) = M_{x \oplus u, u}$ 会退化为单个 Walsh 特征 $\beta_x(z)(-1)^{z \cdot u}$ 。算法通过在零向量和标准基向量上评估 $b_x$ 来恢复相关的 Pauli-Z 部分 $z$ 和系数 $\beta$ 。一个使用随机输入进行的认证步骤用于验证候选解是否并非偶然匹配查询点的退化情况。
解码退化的 $x$ 字符串：
如果一个 $x$ 是“退化的”（即与 $p_x \geq 2$ 个 Pauli 字符串相关联），问题则转化为恢复稀疏的 Walsh-Hadamard 谱。算法采用了 随机折叠（random folding） 技术：
- 它使用一个随机二进制矩阵 $R$ ，将 $n$ 位谱索引 ( $z$ ) 映射到 $m$ 位箱（bins）中，其中 $m \ll n$ 。
- 这种“折叠”能以高概率将单个 $z$ 字符串隔离到“单元素箱（singleton bins）”中。
- 对于单元素箱，算法使用偏移查询来确定 $z$ 字符串的位及其系数。
- 恢复的项从残差函数中减去，然后重复此过程，直到找到该 $x$ 对应的所有项。
- 最后的随机验证过程确保没有遗漏任何项。

核心贡献

算法设计： 本文提出了一种随机化经典算法（算法 1），在 $k$ -稀疏性和稀疏查询访问的承诺下解决了 Pauli 分解问题。
复杂度提升： 不同于现有方法随 $n$ 指数级增长，所提算法实现了在 $n$ 、 $k$ 和 $\log(1/\delta)$ 上的 多项式级查询和运行时间复杂度。
理论保证： 算法对于任何用户选择的 $\delta \in (0, 1)$ 均能以至少 $1-\delta$ 的概率成功。作者为每个阶段（发现、唯一解码和退化解码）的失败概率提供了严格的界限。
稀疏 Walsh-Hadamard 技术： 本研究将布尔立方体中的稀疏恢复技术（特别是稀疏 Walsh-Hadamard 解码）应用于 Pauli 分解背景，利用了随机折叠和基于偏移的位恢复技术。

结果

数值基准测试： 作者在 $n = 2$ $n = 2$ 到 $30 $且$ $且$ k = 2^n$ 的随机实例上测试了该算法。
- 对于较小的 $n$ （ $n < 10$ ），随机化算法的开销使得其速度慢于现有的 PennyLane PauliDecompose 程序。
- 在大约 $n=10$ 时出现交叉点。对于 $n > 10$ ，所提算法显著优于指数时间基准算法。
- 观察到的运行时间和查询计数随 $n$ 呈多项式级增长，与理论界限一致。
- 在所有测试运行中，算法都成功恢复了完整的分解，未发生失败。
可扩展性： 该算法成功处理了高达 $n=30$ 的实例，在此规模下，构建完整矩阵或运行稠密分解算法在计算上已变得难以实现。

意义与声明
本文声称，虽然寻找一般矩阵的 Pauli 分解是指数级困难的，但对于已知在 Pauli 基下是稀疏的矩阵，该问题是 可高效求解的。这一领域对于操作结构化经典输入数据的近程量子算法具有高度相关性。

作者强调，他们的算法是专门为 $k = \text{poly}(n)$ 的 承诺问题 而设计的。他们并未声称能解决通用的稠密情况。其意义在于能够为需要 Pauli 分解的量子算法提供高效的经典预处理，从而可能消除端到端量子工作流中的主要瓶颈。这项工作还突出了特定的应用场景，例如由简洁经典规则定义的矩阵，或由不受信任的服务器持有且仅提供查询访问的数据。

论文以谦逊的态度结尾，指出推导出的上界可能较为宽松，未来的工作可以探索更紧致的界限、下界以及向近似稀疏矩阵的扩展。