Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability

技术摘要：高阶张量核范数与多体可分性的多项式时间算法

问题陈述
本文解决了高维优化和量子信息论中的两个基本计算问题：

1. 核范数弱成员资格判定（Nuclear Norm Weak Membership）： 给定一个张量 $M \in (\mathbb{R}^d)^{\otimes k}$，判定其核范数是否至多为 1，或者其到单位核范数球的距离是否至少为 $\epsilon$。核范数定义为秩一分解中绝对系数之和的下确界。
2. 多体量子可分性（Multipartite Quantum Separability）： 给定一个 $k$-体量子态 $\rho$（通过显式的经典描述或通过未知态的副本提供），判定 $\rho$ 是否是可分的（即为乘积态的凸组合），或者其到可分态集合 $\text{Sep}(d,k)$ 的 Frobenius 范数距离是否至少为 $\epsilon$。

当精度 $\epsilon$ 依赖于维度 $d$，或者当 $k$ 作为输入的一部分出现在特定机制中时，这两个问题已知是 NP-难的。虽然之前的研究在固定 $k$ 或二体情况（$k=2$）下提供了拟多项式算法或多项式时间解法，但对于任意 $k$ 和 $d$ 且具有常数加性精度的一般性多项式时间算法仍然是一个悬而未决的问题。

方法论
作者开发了两种不同的算法框架：一种针对显式给定的张量的经典确定性方法，以及一种针对以副本形式给出状态的量子方法。

1. 经典算法（确定性）
经典方法的核心是一种递归的**谱压缩（spectral compression）**技术，该技术将多线性优化问题视为一个协作的多玩家博弈。

• 谱压缩： 谱压缩不再独立地对 $k$ 个参与者的策略空间进行离散化（这会导致指数级爆炸），而是将前 $j$ 个参与者与剩余 $k-j$ 个参与者之间的相互作用压缩到一个单一的低维“消息”空间 $V_j$ 中。
• 递归前缀压缩： 通过在 $V_{j-1} \otimes H_j$ 与剩余系统之间的切分处应用谱截断（保留仅高于阈值 $\eta$ 的奇异值），他们维持了一个维度为 $O(\eta^{-2})$ 的消息 $p_j$。
• 能量论证（Energy Argument）： 一个关键的技术创新是用于界定累积误差的“能量论证”。通过证明被丢弃分量的平方范数之和呈级数收敛（即其总和等于初始范数），总误差被界定为 $O(\eta\sqrt{k})$，而非直观的 $O(\eta k)$。这使得阈值 $\eta$ 可以设置为 $\Theta(\epsilon/\sqrt{k})$，从而使消息空间的维度相对于 $k$ 是多项式级的。
• 元算法： 该算法迭代地构建可达消息的 $\delta$-覆盖。对于小规模 $k$（$k \le d^2$），它使用局部集合上的凸优化。对于大规模 $k$（$k > d^2$），它将站点分组并在块内进行穷举搜索，利用了局部维度相对于 $k$ 较小的这一事实。
• 归约至弱成员资格判定： 利用 Frank-Wolfe 算法，将对偶优化问题（最大化 $\langle M, \rho_1 \otimes \dots \otimes \rho_k \rangle$）的解转化为核范数和可分性的弱成员资格测试。

2. 量子算法（属性测试）
对于输入为通过副本提供的未知状态 $\rho$ 的情形，作者提出了一种维度缩减协议，该协议避免了学习状态的显式基底。

• 带符号乘积态优化： 该算法将 Bakshi 等人的乘积态学习器扩展到了 qudit 以及带符号目标函数（最大化 $\text{Tr}((\rho - \sigma)\pi)$）。它通过一个局部搜索程序构建了一个小的“重叠乘积覆盖”，该程序能够识别出与目标态具有高重叠度的乘积态，并利用子空间断层扫描和多项式优化来实现。
• 通过滤波进行维度缩减： 算法定义了局部“Frobenius 质量”算符 $A_j = \text{Tr}_{-j}(\rho^2)$。它应用一个量子信道来滤除 $A_j$ 中低于阈值的特征值，从而有效地将状态投影到一个维度为 $q = O(k^2/\epsilon^4)$ 的低维子空间上。
• Schur-Weyl 对偶性： 为了在不显式学习高维基底（这需要 $\text{poly}(d)$ 时间）的情况下实现这种投影，作者利用了 Schur-Weyl 对偶性。通过对 $N$ 个状态副本应用 Schur 变换，他们隔离了置换寄存器与酉表示寄存器。他们丢弃了包含未知基底信息的酉寄存器，并将其替换为一个标准的低维空间，从而有效地执行了对局部酉变换的 Haar 平均。这在保持与可分态距离的同时，将局部维度降低到了 $q$。
• 结果： 随后将缩减后的状态输入低维测试器，从而实现了在运行时和样本复杂度上对 $k$ 和 $\log d$ 呈多项式关系，但与 $d$ 无关的性能。

主要贡献与结果

• 定理 1.1（核范数）： 本文提出了第一个针对高阶张量核范数单位球的确定性多项式时间弱成员资格判定算法，具有常数加性精度。其运行时间为 $d^{O_\epsilon(k)}$。
• 定理 1.2（量子可分性）： 作者提供了第一个针对一般 $k$ 和 $d$ 的多体弱成员资格判定的确定性多项式时间算法（在 Frobenius 范数下），改进了近期仅限于二体情况的结果。其运行时间为 $d^{O_\epsilon(k)}$。
• 定理 1.3（从副本中判定可分性）： 提供了一种量子算法，能够区分可分态与在 Frobenius 范数下距离至少为 $\epsilon$ 的态，该算法使用 $k^{O_\epsilon(1)}$ 个副本，且运行时间为 $k^{O_\epsilon(1)} \cdot \text{polylog}(d)$。这是第一个实现维度无关（dimension-free）测试的弱成员资格测试。
• 技术新颖性： 本工作引入了一种递归谱压缩机制，实现了 $O(\eta\sqrt{k})$ 的误差界限，这与以往限制算法为拟多项式时间的 $O(\eta k)$ 界限形成了对比。此外，它还展示了如何利用表示论（Schur-Weyl 对偶性）来绕过在量子属性测试中显式描述高维子空间的需求。

意义
本文声称解决了在常数精度机制下寻找多体可分性和核范数评估的多项式时间算法这一开放性问题。通过结合协作博弈论视角与谱压缩技术，作者填补了这些问题在拟多项式时间与多项式时间之间的空白。在量子设定中，能够以与局部维度 $d$ 无关（仅为多项式对数因子相关）的副本数和时间来测试可分性，代表了对以往基于二体情况或维度相关算法的重要突破。这项工作强调，跨副本的相干测量对于绕过已知的迹范数（trace-norm）可分性下界是必要的，这为高效的量子属性测试提供了一条新路径。