⚛️ quantum physics

Circuit complexity lower bounds for quantum spin glasses

本文证明了，为随机量子 $p$ -自旋玻璃制备近优基态所需的电路深度，要么随系统规模呈对数增长，要么超过任何固定深度，从而表明浅层电路无法产生必要的纠缠，以弥合乘积态与最优态之间的能量间隙。

原作者： Omar Al-Ghattas, David Gamarnik

发布于 2026-07-17

📖 1 分钟阅读🧠 深度阅读

原作者： Omar Al-Ghattas, David Gamarnik

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

想象一下你正试图建造一座房子。在经典计算的世界里，建造房子就像是在摆放家具：你可以通过一次简单的推动，将一把椅子从厨房移到客厅。这既快速又简单，不需要任何魔法。但在量子世界中，情况大不相同。在这里，“家具”不仅仅是静静地坐在那里；它们是由迷雾构成的，可以同时存在于两个房间中，而墙壁本身也可以以违背常理的方式相互连接。这个被称为“量子信息论”的领域提出了一个宏大的问题：构建一个特定的、复杂的量子态到底有多难？我们称之为“电路复杂度”。这就像是在问：“组装这个复杂的量子拼图，所需的最短、最简单的指令集是什么？”

为什么这很重要？因为宇宙似乎热爱复杂性。一些理论表明，这些复杂量子态的增长与时空中的“虫洞”（即连接宇宙遥远两端的神秘隧道）的增长有关。如果我们能够弄清楚构建这些状态有多难，我们或许能对现实本身的本质产生深刻的理解。然而，这里有一个陷阱。虽然我们知道“随机”量子态极其难以构建（需要指数级的步骤），但我们对自然界实际产生的状态——例如某些随机量子系统的“基态”——却知之甚少。基态是系统能量最低、最稳定的配置，弄清楚如何构建它们是一个核心挑战。

本文通过研究一种特定类型的量子系统——“量子 $p$ -自旋玻璃”来应对这一挑战。可以将这个系统想象成一场由量子粒子进行的、规模巨大的、混乱的“连点成线”游戏。规则是随机的：粒子以 $p$ 个为一组进行相互作用（其中 $p$ 是一个固定的数字，如 3、4 或 5），而它们连接的强度则由掷骰子决定。目标是找到一种能让系统能量最低（或最高，取决于你的计数方式）的粒子排列方式。作者提出了一个非常具体的问题：一个简单的、浅层的量子电路——即一个只有极少层操作的机器——能否构建出一个几乎达到最佳排列效果的状态？

根据本文，答案是否定的。

研究人员证明，对于这些随机量子自旋玻璃，你无法通过一个简单的机器来“作弊”以获得近乎完美的解。他们表明，要达到最佳能量水平所需的“纠缠”（粒子之间那种幽灵般的、深层的联系）过于复杂，以至于无法由浅层电路来创造。即使你给这个电路提供大量的额外辅助粒子（称为“辅助比特”），它仍然会失败。

以下是他们的研究结果分解：

“积态”极限： 首先，他们确定了如果你完全不使用纠缠（只使用简单的、独立的粒子），你只能达到某个特定的低能量水平。这就像尝试用互不连接的砖块来建造摩天大楼；它根本无法支撑起来。
浅层电路的失败： 随后他们证明，即使你允许电路产生一些纠缠，只要该电路是“浅层”的（即其深度仅随粒子数量呈对数级增长，或者仅仅是固定层数），它仍然无法超越那个简单的、无纠缠的极限。
两种情景： 他们研究了这种游戏的两个不同版本。在第一种版本中，每个粒子都与许多其他粒子发生相互作用（一个稠密网络），他们证明任何试图接近最佳能量的电路，其深度必须至少是与粒子数呈对数关系（即 $\log n$ ）。在第二种版本中，粒子仅与少数邻居发生相互作用（一个稀疏网络），他们证明对于你选择的任何固定深度，只要系统足够大且相互作用足够强，该深度的电路根本无法胜任这项工作。

作者对此非常有信心。他们不仅仅是在计算机上进行了模拟；他们提供了数学证明。他们排除了简单、浅层电路能够准备出这些近基态状态的可能性。他们的工作表明，解决这些随机量子谜题所需的“魔法”本质上是深奥且复杂的，这为理解为什么某些量子态如此难以构建——即便对于我们所能想象的最强大的量子计算机而言也是如此——开辟了一条新的路径。

技术摘要：量子自旋玻璃的电路复杂度下界

问题陈述
本文研究了准备量子 $p$ -spin 玻璃近基态（near-ground states）的电路复杂度。这些是随机哈密顿量，其相互作用项通过作用于 $p$ 个量子比特的泡利算符串（Pauli strings）来定义。量子信息论中的一个核心问题是，具有简洁描述的哈密顿量的物理自然态族（例如其基态），是否需要高电路复杂度（特别是高深度）才能进行准备。

最近的研究表明，对于量子 $p$ -spin 玻璃，最优能量与由无纠缠（乘积）态实现的最佳能量之间存在严格的分离。然而，目前尚不清楚浅层电路（例如常数深度或对数深度）能否产生足够的纠缠来弥补这种“乘积态间隙”（product-state gap）。本文探讨了此类浅层电路是否能够准备出能量接近基态最优值的状态。

方法论
作者采用了一种概率方法，将状态准备的下界问题重新表述为对由浅层量子电路索引的高斯过程的一致控制。其核心技术策略是将电路准备状态的能量分解为两个部分：

类乘积项 ( $X_0$ )： 仅由状态的一比特边缘分布决定。无论电路深度如何，该项都受限于乘积态的最优值之上。
残差项 ( $R$ )： 捕捉非乘积、纠缠的 $p$ -点相关性。

作者认为，对于浅层电路，残差项相对于基态能量尺度而言在渐近意义上是微不足道的。证明依赖于三个主要的的技术支柱：

后向支撑（Backward Supports）与依赖图： 作者定义了输出量子比特的“后向支撑”，即在电路回溯过程中可以影响该输出比特的输入量子比特集合。他们构建了一个依赖图，其中顶点是量子比特，若两个量子比特的后向支撑重叠，则存在边。一个关键观察是：如果参与 $p$ -spin 相互作用的量子比特在依赖图中构成一个独立集，则相应的 $p$ -点期望值会发生因子化，导致残差系数消失。
方差缩减： 由于浅层电路的局部性，残差过程的方差显著小于原始能量的方差。具体而言，虽然原始归一化能量的方差阶数为 $1/n$ ，但归一化残差的方差阶数为 $2^D/n^2$ （其中 $D$ 是电路深度）。
熵与覆盖界限： 为了控制残差过程在所有可能电路上的上确界，作者推导了深度为 $D$ 的电路类的一致熵界限。至关重要的是，他们通过将电路“剪枝”到物理输出量子比特的联合后向支撑，并将活跃的辅助量子比特（ancilla qubits）重新标记为一个规范块，从而处理了任意数量的辅助量子比特 ( $r$ ) 的情况。这确保了覆盖数（covering numbers）与 $r$ 无关。

这些界限被应用于三种随机哈密顿量模型中：

平均场（Mean-Field）： 包含所有可能的 $p$ -元组。
增长平均度稀疏（Growing-Average-Degree Diluted）： 一个平均度随 $n$ 增长的稀疏超图。
有界平均度稀疏（Bounded-Average-Degree Diluted）： 一个平均度有界的稀疏超图（项数为线性规模）。

主要贡献与结果
本文为在所有三种机制下、且关于辅助量子比特数量保持一致的近基态准备建立了电路深度下界：

对数深度下界（平均场与增长平均度模型）：
对于足够大的固定 $p$ ，任何准备 $n$ -量子比特状态且其归一化能量在固定正常数范围内的电路，其深度必须至少为 $\Omega_p(\log n)$ 。即使该电路使用任意数量的辅助量子比特，这一结论依然成立。证明表明，对于深度 $D \leq \delta \log n$ 的电路，残差能量过小，不足以弥合乘积态能量与基态能量之间的差距。
固定深度阻碍（有界平均度模型）：
在平均度为有界（项数为线性规模）的机制下，本文证明了固定深度的阻碍。对于每一个固定的深度 $D$ ，存在一个足够大的度预因子 $\zeta$ ，使得没有任何深度为 $D$ 的电路（即使带有任意数量的辅助量子比特）能以高概率准备出近基态。当执行迭代极限 $n \to \infty$ 后再取 $\zeta \to \infty$ 时，成功的概率趋于零。
对辅助量子比特的一致性：
一个重要的技术贡献是，证明了这些下界对于任何数量的辅助量子比特都是一致成立的。以往的计数论证在辅助量子比特相对于系统规模较大时往往无法提供有意义的深度界限；而通过剪枝和重新标记技术克服了这一限制。

意义与与 NLTS 的联系
作者将其结果定位为实现 无低能平凡态（NLTS） 问题的一种概率路径。

对比基于编码的 NLTS： 先前的突破（例如 Anshu, Breuckmann, 和 Nirkhe [6]）证明了针对由量子 LDPC 码构造的哈密顿量的 NLTS 性质。这些构造依赖于交换局部项、无挫折（frustration-free）基空间以及特定的编码理论结构（等周性质）。
随机、非交换环境： 与此不同，本文研究的哈密顿量是随机的、通常是非交换的，并且缺乏已知的有效准备程序。阻碍源于自旋玻璃无序性与浅层电路有限光锥之间的相互作用，而非代码几何结构。
启示： 这些结果为量子 $p$ -spin 玻璃哈密顿量提供了完整的（而非仅仅是组合性的）NLTS 型阻碍（在平均场和增长平均度机制下）。在有界平均度机制下，它们提供了随着度预因子增加而趋向于完整 NLTS 性质的固定深度阻碍。

论文最后猜想，即使使用任意数量的辅助量子比特，近基态的量子 $p$ -spin 玻璃也无法由多项式大小的电路准备，尽管证明这一点需要超出当前范围的技术，可能涉及 BQP 与 QMA 的分离。

类似论文