⚛️ quantum physics

Stratified Sampling for Quasi-Probability Decompositions

该论文提出了一种基于分层采样的通用框架，通过经典动态规划算法对拟概率分解进行优化，在无需额外量子资源的情况下显著降低了量子算法中的配置方差和采样成本。

原作者： Joshua W. Dai, Bálint Koczor

发布于 2026-02-13

📖 1 分钟阅读🧠 深度阅读

原作者： Joshua W. Dai, Bálint Koczor

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

这篇文章主要解决了一个量子计算中的“效率”问题。为了让你更容易理解，我们可以把量子计算想象成在一个充满迷雾的森林里寻找宝藏（计算结果）。

1. 背景：为什么要“随机化”？

在量子计算机上，有些任务非常困难，就像要在迷雾中直接找到宝藏一样，几乎不可能。为了解决这个问题，科学家们发明了一种叫**“准概率分解”（QPD）**的方法。

原来的方法（困难）： 试图直接走一条完美的路，但这条路充满了噪音和错误，走不通。
QPD 的方法（随机化）： 既然完美的路走不通，我们就把任务拆解成很多个**“容易走的短途路线”**。
- 我们不再只走一条路，而是随机选择很多条不同的短途路线（比如：有的路走左边，有的走右边，有的走中间）。
- 每走一条路，我们记录结果，最后把这些结果加权平均起来。
- 神奇的是，虽然单条路是错的，但把它们混合在一起，数学上就能还原出那条“完美路线”的答案。

但是，这里有个大问题：
因为我们要随机选路，所以每次选的路都不一样，导致最后算出来的结果波动很大（方差大）。为了得到准确的结果，我们不得不把每条路走很多很多遍（比如走 100 次、1000 次）来消除这种随机波动。这就像是为了确定一个平均气温，你不得不每天测 1000 次温度，非常浪费时间（计算成本极高）。

2. 核心创新：分层抽样（Stratified Sampling）

这篇文章提出了一种聪明的策略，叫做**“分层抽样”**。

比喻：分班考试 vs. 随机抓人

想象学校要统计全校学生的平均身高。

** naive（朴素/笨办法）：** 你完全随机地在操场上抓人。
- 你可能运气不好，抓了 10 个全是篮球队的高个子，或者全是幼儿园的小朋友。
- 为了得到准确的平均值，你需要抓很多人，而且每次抓的结果波动都很大。
分层抽样（本文的方法）： 你先把学生按年级（一年级、二年级……）分成不同的“层”（Strata）。
- 你知道每个年级大概有多少人（权重）。
- 你按比例从每个年级里抓人。比如一年级抓 10 个，二年级抓 20 个。
- 好处： 你保证了样本的多样性。你不会只抓到篮球队，也不会只抓到幼儿园。这样算出来的平均值更准，而且只需要抓很少的人就能达到同样的准确度。

3. 这篇文章具体做了什么？

作者把这种“分层”的思想用在了量子计算的“随机选路”上。

发现规律： 他们发现，虽然选路是随机的，但很多不同的“路”其实长得非常像。比如，一条路是“左 - 左 - 右”，另一条是“左 - 右 - 左”，它们包含的“左”和“右”的数量是一样的。
建立“计数组”： 他们发明了一种方法，不看路的顺序，只看**“路里包含多少种不同的动作”**。
- 比如：不管顺序如何，只要一条路里有 3 个“动作 A"和 2 个“动作 B"，它们就属于同一个“组”（Stratum）。
智能分配：
- 他们先算出每个“组”大概有多少条路（概率）。
- 然后，他们不再随机乱抓，而是严格按照比例，从每个“组”里抽取固定数量的路去运行。
- 最后，把每个组的结果加起来，就得到了最终答案。

4. 这种方法好在哪里？

更省钱（减少计算量）： 就像上面的分班考试例子，因为样本更有代表性，你不需要跑那么多遍就能得到同样准确的结果。
- 在最好的情况下（没有测量噪音时），这种方法能减少 60% 到 80% 的计算量！
- 即使在最坏的情况下（噪音很大时），也能节省 10% 左右的计算量。
不需要新硬件： 这是一个纯软件层面的优化。你不需要买更贵的量子计算机，也不需要改变量子电路本身，只需要在运行前的准备阶段（经典计算机上）算一下怎么分配，然后在运行后的数据处理阶段（经典计算机上）把结果加权平均即可。
保证不更差： 作者证明了，这种新方法绝对不会比原来的笨办法更差。在最坏的情况下，它和笨办法一样；在大多数情况下，它都更好。

5. 总结

这就好比你要做一道复杂的菜（量子计算）：

以前： 你随机抓一把食材（随机选路），发现味道忽咸忽淡，为了尝出准确的味道，你得做 100 次菜。
现在（本文）： 你先看看冰箱里有什么（分类），然后按比例从每种食材里拿一点（分层抽样）。这样你只需要做 20 次菜，就能得到和做 100 次一样准确的味道。

一句话总结：
这篇文章提出了一种聪明的“分配策略”，让量子计算中的随机实验不再“盲目乱撞”，而是“有的放矢”，从而在不增加硬件成本的情况下，大幅降低了获得准确结果所需的计算时间和资源。这对于未来的量子计算机（尤其是早期的容错计算机）来说，是一个非常重要的效率提升。

这篇论文提出了一种名为分层采样（Stratified Sampling）的新框架，用于优化准概率分解（Quasi-Probability Decompositions, QPDs）中的采样过程。QPD 是量子算法和协议（如误差缓解、概率合成等）中的核心技术，但传统的“朴素采样”（Naïve Sampling）会引入额外的配置方差（Configuration Variance），导致采样成本增加。

以下是该论文的详细技术总结：

1. 问题背景 (Problem)

QPD 的局限性：QPD 通过将“困难”的量子电路分解为一系列“容易”的电路变体的加权组合来工作。然而，为了保持无偏性，必须引入随机化（在不同电路变体间采样）。
方差来源：最终的估计量方差由两部分组成：
1. 玻恩规则散粒噪声（Born-rule shot noise）：量子测量固有的随机性。
2. 配置方差（Configuration variance）：由于在不同电路变体（配置）之间进行经典随机化而产生的额外方差。
现有挑战：虽然 QPD 能减少量子资源需求，但配置方差会导致所需的总采样次数（电路执行次数）显著增加，其开销通常随电路深度呈指数级增长（由 QPD 的 1-范数 $\|g\|_1$ 决定）。现有的优化主要集中在改进 QPD 分解本身（减小 $\|g\|_1$ ），而忽略了在固定分解下如何更高效地采样配置。

2. 方法论 (Methodology)

作者将 QPD 估计视为一个两层蒙特卡洛估计问题，并引入了经典统计学中的分层采样技术来减少配置方差。

方差分解：利用全方差定律（Law of Total Variance），将总方差分解为“层内方差”（给定配置下的玻恩噪声）和“层间方差”（不同配置间的均值差异）。
$\text{Var}(Y) = E[\text{Var}(Y|\ell)] + \text{Var}(E[Y|\ell])$
分层采样的目标是消除或减少第二项（配置间的方差）。
计数向量分层（Counts-Vector Stratification）：
- 统计量选择：作者提出使用**计数向量（Counts Vector）**作为分层统计量 $S(\ell)$ 。对于一个由 $\nu$ 个局部门组成的电路，如果每个门有 $d$ 种可能的实现（基元），配置 $\ell$ 是一个长度为 $\nu$ 的索引序列。计数向量 $M = (M_1, \dots, M_d)$ 记录了每种基元出现的次数，而忽略了它们在电路中的具体位置。
- 优势：许多 QPD 方案（如概率误差消除 PEC 和概率角度插值 PAI）具有置换对称性。相同计数向量的配置往往具有相似的期望值，因此将它们归为一层（Stratum）可以显著降低层间方差。
动态规划（Dynamic Programming, DP）实现：
- 为了实施分层采样，需要知道每个层的权重（概率）以及如何在给定计数向量的条件下高效采样配置。
- 作者设计了一个前向动态规划算法，用于精确计算所有计数向量层的权重（基于泊松 - 多项分布 PMD）。
- 设计了一个后向采样算法，利用缓存的 DP 表，在给定计数向量的条件下，以 $O(\nu d)$ 的时间复杂度生成具体的电路配置。
- 整数分配与残差处理：由于实际采样次数必须是整数，作者采用了汉密尔顿分配法（Hamilton Apportionment）结合残差桶（Residual Bucket）策略，确保在有限采样次数下估计量依然是无偏的。

3. 主要贡献 (Key Contributions)

理论保证（“永不劣于”定理）：
- 证明了在理想的比例分配（Proportional Allocation）下，基于任何统计量的分层采样估计量都是无偏的。
- 证明了在固定配置预算下，分层采样的方差永远不会比朴素采样差（ $\text{Var}_{\text{strat}} \le \text{Var}_{\text{naive}}$ ），且只要层间均值不完全相同，方差就会严格降低。
- 方差减少量等于被统计量解释的层间方差部分。
通用算法框架：
- 为任意乘积形式（Product-form）的 QPD 构建了一个通用的分层采样框架。
- 提出了基于计数向量的具体实现，并给出了高效的经典预处理（DP）和条件采样算法。
- 该方法是“即插即用”的（Drop-in replacement），不需要额外的量子资源，仅需经典预处理和采样逻辑的修改。
复杂度分析：
- 预处理时间复杂度为 $O(d \nu^d)$ ，空间复杂度为 $O(\nu^d)$ （对于固定的局部宽度 $d$ 和电路深度 $\nu$ ）。
- 虽然对于极大的 $d$ 或 $\nu$ 可能面临内存挑战，但在当前近中期（NISQ）和早期容错算法的典型参数范围内是可行的。

4. 实验结果 (Results)

作者在横场伊辛模型（TFIM）的 Trotter 演化上，针对两种典型的 QPD 方案进行了数值模拟：

概率角度插值（PAI）：用于在离散角度硬件上模拟连续旋转。
概率误差消除（PEC）：用于抵消单比特去极化噪声。

关键发现：

Oracle 模式（无散粒噪声）：在配置方差主导的情况下（即理想情况），分层采样带来了巨大的方差降低，减少了 60% - 80% 的总方差。
单次射击模式（Single-shot, R=1）：在散粒噪声主导的悲观情况下，依然观察到了稳健的约 10% 的方差降低。
中间模式（R=64）：展示了从 Oracle 到单次射击模式的平滑过渡。
结论：分层采样显著降低了达到相同精度所需的电路执行次数（配置预算），从而扩展了 QPD 方法在实际应用中的有效范围。

5. 意义与展望 (Significance & Outlook)

资源节省：该方法不需要额外的量子硬件资源，仅通过优化经典采样策略，就能显著降低近中期和早期容错量子计算中的采样成本。
通用性：该框架不仅适用于 QPD，原则上可推广到任何涉及电路随机化的量子协议（如随机编译、经典阴影等）。
未来方向：
- 探索更粗粒度的统计量（如符号奇偶性）以平衡预处理成本和方差降低效果。
- 结合自适应采样（Pilot/Neyman allocation）进一步优化。
- 处理更深电路时的可扩展性问题（通过剪枝或近似）。

总结：这篇论文通过引入经典统计学的分层采样思想，成功解决了 QPD 协议中配置方差过高的问题。它提供了一种理论上有保证、算法上可实现的通用方案，能够在不增加量子开销的前提下，显著降低量子算法的采样成本，对于提升近中期量子计算的实用性具有重要意义。