A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics

技术摘要：噪声量子电路的多项式时间经典采样

问题陈述
本文探讨了在存在噪声的情况下，确定量子优势极限的挑战。虽然理想的量子计算机可以实现对经典计算机的指数级超越，但实验设备受限于噪声，这通常会降低计算能力。现有的针对一般噪声电路的经典模拟方法通常要求电路深度随系统规模呈超对数增长（$d \sim \omega(\log n)$），噪声才能使全局状态趋于平凡的均匀分布。一个关键的开放性问题仍然存在：在噪声强度非零的情况下，能否在与系统规模无关的深度（常数深度）下，对噪声量子电路进行经典模拟？具体而言，作者研究了在输出分布收敛至均匀分布之前，是否存在一种“最坏情况”下的噪声几何局部量子电路是可被经典模拟的。

方法论
作者开发了一种结合了统计力学和量子信息论技术的新型经典采样算法。其核心方法论包含三个主要步骤：

1. 映射至聚合物模型（Polymer Models）：
   作者将噪声量子电路输出分布的边缘概率映射为统计力学中一个抽象聚合物模型的配分函数。

   • 他们将晶格分解为边长为 $2d$ 的粗粒化块（blocks）。
   • 他们将“聚合物”定义为这些块构成的连通集合。
   • 聚合物的权重通过限制在聚合物支撑集上的 Pauli 可观量的海森堡演化来定义。
   • 由于电路的几何局部性，不相邻的块具有不相交的后向光锥，因此配分函数可以分解为对兼容（不重叠且不相邻）的聚合物配置之和。

2. 截断簇展开（Truncated Cluster Expansion）：
   为了计算配分函数（以及由此得到的对数边缘概率），作者采用了簇展开技术。该技术将配分函数的对数展开为一系列“簇”（clusters）的聚合物之和。

   • 算法通过仅对支持在 $O(\log n)$ 个块上的簇进行求和来截断此展开。
   • 这种近似的准确性依赖于“权重衰减”性质：即聚合物的贡献必须随其尺寸（块的数量）呈指数级衰减。

3. 通过超收缩性（Hypercontractivity）证明权重衰减：
   其核心技术贡献在于证明了当电路深度 $d$ 超过一个独立于系统规模的临界阈值时，聚合物权重会呈指数级衰减。

   • 作者利用了量子超收缩性以及去极化通道（depolarizing channels）的 $\ell_2$-范数收缩界限。
   • 他们构建了一条范数转换路径：从 $\ell_\infty$ 范数开始，经过 $\ell_{1+(4d)^D}$ 和 $\ell_2$ 范数，最后回到 $\ell_1$ 范数。
   • 通过应用超收缩性在不同范数之间进行转换，并利用去极化通道的收缩性（事实 5.2），作者证明了噪声会在局部累积。由于系统的几何局部性，噪声引入的熵（随体积缩放）无法以同等速度逃逸（后者随边界缩放），从而导致了一个局部的“高温相”，其中相关性呈指数级衰减。

核心结果
论文确立了以下主要定理（非正式表述）：

• 定理： 对于任何由单比特去极化噪声（在每层之后施加强度为 $p$ 的噪声）组成的、由幺正操作构成的几何局部量子电路，存在一个多项式时间经典算法，可以在满足以下条件的条件下，以逆多项式全变差距离（以及边缘概率的相对误差）进行输出分布的采样，其中电路深度 $d$ 满足：
  $$d > d_{crit} = O(p^{-1} \log p^{-1})$$
• 算法能力： 所提供的算法是任意边缘概率的完全多项式时间近似方案（FPTAS）。它实现了相对误差采样，而这一任务在无噪声电路以及噪声强度在 $O(p^{-1})$ 深度阈值以下的噪声电路中被认为是经典计算难以实现的。
• 复杂度区间： 该结果识别了噪声电路复杂度图谱中的一个新区间。此前的工作表明，在深度高达 $O(p^{-1})$ 时存在硬度，且对于深度为 $\log n$（或 $\omega(\log n)$）的电路是可模拟的；而这项工作证明了一旦深度超过 $O(p^{-1} \log p^{-1})$，即可在常数深度下实现模拟。

意义与主张
作者认为，其工作为以下观点提供了更充分的理由：即若要实现随系统规模缩放的计算深度，非幺正（non-unital）或非局部资源（如带有反馈的中途测量或量子比特复位）是根本必要的。

• 量子-经典转换： 论文将这一结果解释为由开放量子系统中热量（熵）的累积所驱动的“量子-经典转换”。作者指出，如果没有低热库（low-temperature bath）来排出热量（即缺乏非幺正操作），系统会在达到临界深度后自然过渡到经典可模拟的高温相。
• 紧致性： 作者指出，其界限在对数因子范围内是紧致的，因为在低于 $O(p^{-1})$ 的深度下，相对误差采样已被证明是困难的。
• 普适性： 该结果适用于所有具有幺正操作和去极化噪声的几何局部量子电路，涵盖了此前仅限于特定门集或特定噪声模型的成果。
• 哲学背景： 这项工作探讨了“自身”开放量子系统的计算复杂度，表明噪声多体系统的自然动力学在达到临界深度后，会表现出一种可以利用统计力学工具进行严格表征的向经典性转变的过程。

本文并不声称要模拟特定的实验设备或提出新的硬件，而是为一类广泛的噪声量子动力学提供了理论上的可模拟性界限，表明此类系统中的“量子优势”是脆弱的，且仅限于浅层深度，除非采用特定的非幺正误差纠正机制。