Schatten norms and determinants of linear combinations of matrix tensor powers via virtual representations

技术摘要：通过虚表示计算矩阵张量幂线性组合的 Schatten 范数与行列式

问题陈述
本文解决了计算矩阵张量幂线性组合的 Schatten $p$-范数（$0 < p < \infty$）和行列式的计算挑战。具体而言，给定固定的矩阵 $A_1, \dots, A_s \in M_d(\mathbb{C})$ 和标量 $t_1, \dots, t_s \in \mathbb{C}$，目标是计算如下算子的量：
$$X_n = \sum_{i=1}^s t_i A_i^{\otimes n}$$
当 $n$ 增长时，其维度为 $d^n$。直接进行稠密计算在 $n$ 增大时会呈指数级增长。虽然 $s=1$（单项）和 $s=2$（两项）的情况存在初等约减方法（例如通过特征值或谱分解），但对于 $s \ge 3$ 的情况，不存在此类约减。这种困难性在量子假设检验问题中得到了体现，该问题需要区分两个状态的混合与第三个状态，这要求评估三项组合的迹范数。

方法论
作者提出了一种精确的表示论方法，避免了构建完整的 $d^n \times d^n$ 矩阵。该方法依赖于三个主要支柱：

1. 同步酉分块分解（Simultaneous Unitary Block Decomposition）：
   利用 Schur–Weyl 对偶性，作者为任意矩阵（包括奇异矩阵和非正规矩阵）建立了同步酉分解。对于任何 $A \in M_d(\mathbb{C})$，其张量幂 $A^{\otimes n}$ 单位等价于由 Schur 模 $S_\lambda(A)$ 与单位矩阵的张量积构成的直和，其中索引为具有至多 $d$ 个部分的 $n$ 的分划 $\lambda$。该分解源自紧群 $U(d)$，并通过复化和多项式连续性扩展到 $M_d(\mathbb{C})$。

2. 虚表示与加法性（Virtual Representations and Additivity）：
   该方法利用了多项式表示的 Grothendieck 环。作者并没有显式地构造不可约 Schur 模（因为这可能非常繁琐），而是使用 Jacobi–Trudi 恒等式 将 Schur 模表示为对称幂张量积的符号虚组合（差值）。

   • 对于加法泛函（$p < \infty$ 时的 Schatten $p$-范数），该泛函在正交直和上具有加法性。这使得作者可以将 Schur 模替换为其虚分解，从而将问题转化为更简单的对称幂项的符号 Schatten 范数之和。
   • 对于乘法不变量（行列式、特征多项式），虚系数变为整数指数，从而允许将 Schur 模的行列式表示为对称幂项行列式的乘积（或商）。

3. 显式对称幂构造（Explicit Symmetric Power Construction）：
   核心计算步骤涉及评估对称幂 $\text{Sym}_k(A)$。作者提供了一个在归一化占据数基底下的 $\text{Sym}_k(A)$ 矩阵元显式公式，该公式表示为 $A$ 的矩阵元之单项式的稀疏线性组合。这使得预计算稀疏系数表成为可能，从而提高了在线评估的效率。

主要贡献
本文做出了四个主要贡献：

• 理论框架： 证明了对所有 $A \in M_d(\mathbb{C})$ 都有效的同步酉 Schur–Weyl 分块分解，并展示了如何通过表示环恒等式导出加法 Schatten 泛数和乘法不变量的精确恒等式。
• 主公式（Master Formula）： 推导出一个“主公式”（定理 4.1），该公式将 $X_n$ 的 Schatten 范数计算简化为对符号化的线性组合的对称幂 Schatten 范数的求和。对于 $d=3$，每个 Schur 项都简化为两个显式可计算的对称幂项之差。
• 算法实现： 描述了一个实用的算法实现（tensorpow Python 包），其特点是具有稀疏单项式表、系数矩阵、对称幂缓存以及通过聚合相同的虚块来减少冗余计算的功能。
• 复杂度分析： 确定了对于固定维度 $d$，最坏情况下的稠密算术复杂度为 $O(n^{3(d-1)^2 + d - 1})$，峰值存储空间为 $O(n^{2(d-1)^2})$。对于固定的维度，这代表了一个关于 $n$ 的多项式时间算法，与直接方法的指数级复杂度形成对比。

结果与基准测试
作者使用 tensorpow 工具包（版本 0.3.0/0.4.2）在 $3 \times 3$ 矩阵上验证了该方法：

• 内存缩减： 对于 $n=18$ 且 $d=3$ 的情况，未约减的矩阵阶数为 $3^{18} \approx 3.87 \times 10^8$（稠密存储需要约 $2.4 \times 10^{18}$ 字节），而约减后的方法操作的符号块最大阶数仅为 18,496。
• 性能： 一个真实的针对 $n=18$ 的三项迹范数问题在单个 CPU 线程上约 47.6 秒内完成评估。相比之下，直接的稠密构造在 $n=8$ 到 $n=9$ 之间变得不可行（运行时间从 $\sim 100$ 秒跳升至 $\sim 2800$ 秒）。
• 准确性： 在 $n \le 9$ 时，约减方法与直接计算之间的相对误差低于 $3.4 \times 10^{-15}$。
• 可扩展性： 该方法支持对 $3 \times 3$ 矩阵高达 $n=30$ 的输入，此时未约减的矩阵阶数超过 $2 \times 10^{14}$。

意义与主张
本文声称，该方法提供了计算涉及三个或更多张量幂项问题的（如量子信息理论中的复合假设检验场景）有限拷贝表达式的第一种实用方法。

• 它填补了初等约减（适用于 $s=1, 2$）与难以处理的一般情况之间的空白。
• 它使得对“三项”领域的数值探索成为可能，该领域此前缺乏通用的单字母渐近公式，且在计算上是难以企及的。
• 作者强调，虽然该方法并不提供新的渐近公式，但它使得对精确有限 $n$ 量值的数值评估能够远超暴力破解的极限。
• 该方法在表示环中是精确的，尽管作者指出必须监控数值稳定性（特别是符号求和中的抵消问题），并为此提供了诊断工具。

这项工作被呈现为一种用于大规模张量幂计算的实用新方法的开发，它将之前的 $2 \times 2$ 实现扩展到了第一个真正困难的情况（$d=3$），并建立了一个对任意固定 $d$ 都有效的框架。