⚛️ quantum physics

Semidefinite extension complexity of the separable set, with applications to approximate disentanglers

本文为近似优化问题中可分量子态集的半正定扩展复杂度建立了超多项式下界，证明了任何具有均匀加性误差 $a$ 的半正定规划所需的规模至少为 $d^{c_\theta\min\{a^{-1/3},d^\theta\}}$ ，从而改进了之前的拟多项式界限。

原作者： Sevag Gharibian, Carsten Hecht, Dorian Rudolph

发布于 2026-09-09

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Sevag Gharibian, Carsten Hecht, Dorian Rudolph

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

在量子世界中，信息存储在可以同时存在于多种状态中的粒子中，这种特性被称为叠加（superposition）。当两个这样的粒子相互连接时，它们会形成一个纠缠对，无论距离多远，都表现为一个单一的单元。这种纠缠是最强大的理论量子计算机背后的引擎，使它们能够解决经典机器需要永恒时间才能解决的问题。然而，有一种特定的量子证明系统，用于验证复杂的计算，它依赖于另一种资源：非纠缠证明。在这种情景下，验证者接收到两份彼此独立的信息，就像两个从未谋面且没有任何秘密联系的陌生人一样。该领域的中心谜题在于，一个只能检查这些独立证明的验证者，是否实际上与一个可以检查纠缠证明的验证者一样强大。如果它们同样强大，这意味着这种奇特的、非局域性的纠缠连接对于这种特定类型的验证而言，并不提供根本性的优势。

为了测试这一点，研究人员长期以来一直在寻找一种“解纠缠器”（disentangler），这是一种理论上的机器，可以将任何量子态（即使是高度纠缠的量子态）转化为看起来像是两个独立部分的量子态。如果这样一种机器存在并且能够以可控的资源量构建，它将证明独立证明系统与纠缠证明系统一样强大。人们曾希望这种机器可以充当一座桥梁，允许更简单的系统模拟更复杂的系统。多年来，科学家们一直在思考，这座桥梁能否用合理的量子比特数量来构建，或者这项任务是否过于困难，以至于需要一台无法想象的庞大机器。

一组研究人员现在为这个问题提供了一个明确的答案，证明了这样一座桥梁无法用合理的资源来构建。他们证明，任何试图将任意量子态转换为独立量子态的机器，其使用的输入比特数必须随输出规模呈超多项式级增长。在实际操作中，这意味着随着量子系统稍微变大，用于解纠缠的机器也会变得天文数字般庞大，迅速超过任何可以想象的物理设备的容量。这一发现有效地排除了使用解纠缠器来证明独立证明系统等同于纠缠证明系统的策略。研究人员不仅是提出了这种观点，还构建了一个严密的数学证明，表明这种机器的大小从根本上受到几何学和概率定律的限制，而不仅仅是当前的工程约束。

他们发现的核心在于对“可分态”（separable states）的研究，即那些可以被描述为独立部分简单组合的量子态。研究人员专注于利用一种特定类型的数学优化方法，来区分这些可分态与其他所有可能的量子态。他们表明，任何尝试使用一种标准的数学工具（称为半正定规划，semidefinite program）来近似可分态行为的尝试，都需要一个如此庞大的结构，以至于在处理大型系统时变得毫无用处。为了直观理解，请想象尝试用一张平面的二维地图来描述一个复杂的高维物体的形状。研究人员证明，无论你多么巧妙地绘制这张地图，如果你想要它足够精确且具有实用价值，那么地图本身必须大得离谱。

通过分析机器规模与转换精度之间的关系，团队发现了一个严格的权衡。如果允许机器在转换过程中产生哪怕极其微小的误差，机器的规模仍然会以过快且不切实际的速度增长。具体而言，他们表明，对于一个具有特定输出比特数的系统，解纠缠器所需的输入比特数必须随输出规模的幂次呈指数级增长，而不仅仅是简单的倍数关系。这意味着，即使输出规模翻倍，输入机器的大小也不仅仅是翻倍；它会乘以一个剧烈增加的因子。这一结果在机器被允许具有轻微误差的情况下依然成立，而这种误差程度对于任何现实世界的应用都是必要的。

这项工作的意义超越了特定的证明系统问题。它确立了在不丢失本质属性的情况下，我们可以压缩或简化量子信息的根本极限。研究人员还确认，他们的发现适用于更广泛的数学模型，表明这种难度并非仅仅是某个特定算法的特质，而是量子世界的一种深层属性。他们利用了一种涉及“伪密度”（pseudo-densities）的技术——这是一种在行为上类似于概率分布但允许某些负值的数学构造——来揭示问题的隐藏复杂性。这种方法使他们能够证明，任何试图用更简单的结构来近似可分集的尝试，都会随着系统规模的扩大而必然失败。

在更广泛的科学界背景下，这一结果解决了关于非纠缠证明能力的长期争论。虽然它并没有证明两种系统在所有可能的情景下都是不同的，但它证明了使用解纠缠器来使两者等效的特定策略是不可能的。这迫使研究人员寻找其他方法来理解纠缠信息与非纠缠信息之间的关系。这项工作也突显了量子系统内在的巨大复杂性，表明即使我们试图剥离纠缠，其底层结构仍然难以用简单的工具来捕捉。

论文最后指出，虽然他们的结果对其中一种特定方法构成了强力的阻碍，但并未关闭关于这两个证明系统是否相等的整个问题的门。其他方法可能仍然存在，但通过解纠缠器这条路径现在已被已知是被一堵不可逾越的复杂性之墙所阻断。研究人员的工作为这一障碍提供了一张精确的定量地图，展示了这堵墙到底有多高，以及为什么无法攀爬。他们的发现得到了形式化计算机检查证明的支持，确保了逻辑在最严格的审查下依然成立。这种确定性为科学界提供了一个坚实的基石，使人们知道他们发现的极限是真实的，而非仅仅是某个特定计算的产物。

最终，这项研究描绘了一个量子世界的图景：在满足某些条件时，操纵信息所需的资源不仅是巨大的，而且是呈指数级增长的。这表明，纠缠的力量并不是可以通过支付极高的代价就能轻易模拟或被独立部分所取代的。对于研究计算极限的人来说，这是拼图中的关键一块，定义了对于依赖独立证明的机器而言，什么是可能的，以及什么将永远处于触及不到的范围之外。这项工作不仅仅是回答了一个问题，它还重新定义了问题的景观，表明其地形比此前想象的要更加崎岖。

技术摘要：可分集（Separable Set）的半正定扩展复杂度

1. 问题陈述

本文研究了在可分态集 $\text{Sep}(d:d)$ 上近似最大接受概率 $h_{\text{Sep}}(Q)$ 的计算复杂度。该优化问题定义为 $h_{\text{Sep}}(Q) = \max_{\sigma \in \text{Sep}(d:d)} \text{Tr}(Q\sigma)$ ，它是复杂度类 $\text{QMA}(2)$ （具有两个不纠缠证明的量子 Merlin-Arthur）的核心。

研究重点是在 Harrow, Natarajan, 和 Wu (HNW) 建立的框架内，探讨可分集的半正定扩展复杂度（semidefinite extension complexity）。作者研究了在满足以下约束的情况下，近似 $h_{\text{Sep}}$ 所需的最小半正定规划（SDP）规模 $r$ ：

公共可行域： 所有测量算符 $Q$ 共享一个单一的 SDP 可行域 $\mathcal{P}$ （一个由 $r \times r$ 半正定矩阵组成的谱锥）。
目标无关嵌入： 存在一个固定的映射 $\iota$ ，将纯积态嵌入到 $\mathcal{P}$ 中，使得对于任何 $Q$ ，SDP 目标函数 $\Phi_Q$ 都能重现接受概率 $\text{Tr}(Q\tau)$ 。
近似： 该 SDP 必须在指定的加性误差 $a$ 或相对间隙 $\varrho$ 内近似 $h_{\text{Sep}}$ 。

此外，本文将这些下界应用于近似解纠缠器（approximate disentanglers），即量子信道 $\Lambda: \mathcal{L}(\mathbb{C}^D) \to \mathcal{L}(\mathbb{C}^d \otimes \mathbb{C}^d)$ ，这类信道能将任意输入映射为接近可分态的状态，并覆盖所有可分态。其目标是确定此类信道所需的最小输入维度 $D$ 。

2. 方法论

作者结合使用了模式矩阵下界（pattern-matrix lower bounds）、伪密度技术（pseudo-density techniques）以及谱锥几何（spectrahedral geometry）。

2.1 HNW 框架与 PSD 秩

核心技术依赖于 Lee–Ragavendran–Steurer (LRS) 定理，该定理将 SDP 表述的大小与特定非负矩阵（“松弛矩阵”）的 PSD 秩联系起来。

松弛矩阵构造： 作者构造了一个矩阵 $M$ ，其行对应于“见证者”（块正算符 $W_T$ ），列对应于“态”（积态 $\sigma_S$ ）。矩阵项为 $M(T, S) = \text{Tr}(W_T \sigma_S)$ 。
分解： 一个规模为 $r$ 的 SDP 意味着该矩阵存在一个大小为 $r+1$ 的 PSD 分解。因此，通过对 $M$ 的 PSD 秩进行下界估计，可以得出对 SDP 规模的下界。

2.2 背包模式矩阵（Knapsack Pattern Matrix）

不同于以往 HNW 利用基于图 3-着色性的 QMA(2) 协议的做法，本文基于**中心背包多项式（central knapsack polynomial）**构造了一个矩阵：
$f_m(x) = \frac{1}{m^2} \left[ \left( \sum_{i=1}^m x_i - \frac{m}{2} \right)^2 - \frac{1}{4} \right]$
其中 $m$ 是一个奇整数。在布尔超立方体 $\{0,1\}^m$ 上， $f_m(x) \geq 0$ 。然而，Grigoriev 的伪期望泛函 $\mathcal{G}_m$ 在处理不存在的汉明重量层 $m/2$ 时，会赋予 $f_m$ 一个负值（具体为 $-1/4m^2$ ）。

2.3 通过切比雪夫多项式进行放大

为了处理比 HNW 的指数级微小误差更大的情况（如常数或反多项式误差），作者应用了切比雪夫-哈达玛放大（Chebyshev-Hadamard amplification）：

他们对矩阵项应用多项式变换 $P_\ell(u) = (1 + T_\ell(2u-1))/2$ 。
该变换在保持 $[0,1]$ 范围内项的非负性的同时，将“形式上的”负点处的负伪期望值放大了 $\ell^2$ 倍。
至关重要的是，作者利用恒等式 $P_\ell(u) = u Q_\ell(u)^2$ 来限制 PSD 秩的增长，证明了 PSD 秩的成本仅随多项式的次数线性增长，从而使该论证能够适用于更大的误差参数。

2.4 见证者与态的构造

命题 4.1 明确构造了：

积态： 使用特定的基向量叠加来编码子集 $S \subseteq [N]$ 的 $\sigma_S$ 。
块正见证者： $W_T$ 由对角投影算符和一个涉及交换算符 $F$ 的惩罚项组成。这些见证者被设计为在积态上是非负的，但可以在纠缠态上取负值，且其范数界限为与环境维度无关的 $O(m)$ 。

3. 核心贡献与结果

3.1 SDP 表述的下界

本文为近似 $h_{\text{Sep}}$ 的 SDP 表述规模 $r$ 建立了一个新的下界。

定理 5.4： 对于任何固定的 $0 < \theta < 2/7$ ，存在常数 $c_\theta, a_\theta > 0$ ，使得对于足够大的 $d$ 以及近似误差 $a \leq a_\theta$ ，任何近似 $h_{\text{Sep}}$ 到误差 $a$ 的 SDP 规模满足：
$r \geq d^{c_\theta \min\{a^{-1/3}, d^\theta\}}$
与 HNW 的比较： HNW 证明了对于误差 $O(1/d^2)$ ，下界为 $d^{\log d / \text{polylog} \log d}$ 。本文的新界限适用于常数误差，并且当误差足够小时（ $a \leq d^{-3\theta}$ ），将 HNW 的界限提升到了 $d$ 的幂次的指数级（即 $d^{\Omega(d^\theta)}$ ）。
几何解释： 推论 5.6 将此扩展到谱锥阴影（spectrahedral shadows），证明任何包含 $\text{Sep}(d:d)$ 且与其在迹距离 $a$ 内的凸态集，其谱锥提升（spectrahedral lift）的大小至少为 $d^{c_\theta \min\{(2a)^{-1/3}, d^\theta\}}$ 。这为 Fawzi 关于可分集没有精确半正定表示的定理提供了定量化的对应。

3.2 近似解纠缠器的下界

作者将 SDP 下界应用于近似解纠缠器的输入维度 $D$ 。

定理 1.1： 对于一个 $(\varepsilon, \delta)$ -近似解纠缠器，其总误差为 $a = \varepsilon + \delta$ ，则输入维度 $D$ 满足：
$\log D \geq c M_a \log(2 + R_a)$
其中 $M_a$ 和 $R_a$ 是由 SDP 界限导出的关于 $d$ 和 $a$ 的函数。
推论 1.2（定量增长）：
- 如果 $a \leq n^{-c}$ （相对于量子比特数 $n = \log d$ 的反多项式），则 $\log D = \Omega(n^{1+c/3})$ 。这强制要求了超线性数量的输入量子比特。
- 如果 $a$ 的阶数为 $(\log d)^{18/7} / d^{6/7}$ ，则 $\log D = \Omega(d^{2/7} / (\log d)^{6/7})$ 。
对 QMA(2) 的意义： 这些结果排除了当承诺间隙（promise gap）为超多项式级（ $n^{-\omega(1)}$ ）时，利用解纠缠器策略来证明 $\text{QMA} = \text{QMA}(2)$ 的可能性，因为这种策略需要超多项式数量的输入量子比特。

3.3 玻色子可分性

推论 5.7 将这些下界扩展到两粒子玻色子可分体（形式为 $|\psi\rangle\langle\psi|^{\otimes 2}$ 的态），表明相同的复杂度界限同样适用。

4. 重要性与主张

本文提出了以下重要性：

针对 SDP 的特定下界： 本工作首次为近似可分集的 $h_{\text{Sep}}$ 的通用 SDP 扩展表述提供了无条件的信息论下界。虽然 Bostanci 等人 [BGH+26] 的并行工作通过量子 Oracle 分离为近似解纠缠器建立了更强的下界（超越了定理 1.1 中的解纠缠器界限），但其归约方法并不适用于通用的 SDP 表述。因此，在半正定复杂度语境下，针对 SDP 特定表述的下界（定理 5.4 和推论 5.5）仍是本文的主要贡献。
定量改进： 这些界限显著改进了 HNW 的结果，将对于常数或反多项式误差的界限从拟多项式（quasipolynomial）提升到了 $d$ 的指数级。
对解纠缠器策略的反驳： 结果表明，如果信道误差相对于承诺间隙足够小（特别是在 SDP 界限适用的范围内），那么解纠缠器方法无法使用多项式数量输入量子比特的信道来模拟 $\text{QMA}(2)$ 。
方法论进步： 本工作引入了对 LRS 定理更精细的应用，利用背包多项式和切比雪夫放大，与以往基于协议的构造相比，能够更精确地控制误差参数和 PSD 秩成本。

作者承认 Bostanci 等人 [BGH+26] 的并行工作利用量子 Oracle 分离证明了更强的解纠缠器下界（对于常数误差 $\log D = \Omega(\sqrt{d})$ ），但作者指出，Bostanci 等人的归约并不适用于通用的 SDP 表述，因此，针对 SDP 特定表述的下界（定理 5.4 和推论 5.5）仍然是本文的核心贡献。研究结果得到了 Lean 形式化证明的支持。