Mixed symmetries of S_n: immanants in the sampling of U(d) submatrices

本文基于 Trevor Welsh 在 2025 年 7 月于布拉格举行的 ISQS29 上的报告，展示了关于 Haar 分布酉矩阵系中子矩阵余子式之均值及高阶矩的结果。

要点

想象你有一副巨大的、完美洗牌的扑克牌，但它不是 52 张牌，而是有 $d$ 张牌，它们排列在一个被称为“酉矩阵”（unitary matrix）的复杂多维网格中。这个网格代表了一个量子系统，其中一切都根据概率规则（Haar 测度）实现了完美的混合。

现在，想象你伸手从这个网格中切出一个小小的正方形部分，比如一个 $n \times n$ 的区域。题目提出了一个非常具体的问题：如果你计算这个小部分的一个特殊数值（称为“不变式” immanant），如果你不断抽取新的随机部分，这个数值的平均值大约是多少？

以下是使用简单类比对该论文研究结果的解析：

1. 三种类型的“数值”（行列式、永恒式与不变式）

要理解这篇论文，首先需要了解作者正在测量的三种数值类型。可以将它们视为在你的 $n \times n$ 网格中进行的一场游戏的得分方式：

• 行列式（Determinant，即“反社交”得分）： 这是一个经典的数学公式，它通过加总数字的乘积，但会根据严格的规则减去其中的某些项。这就像一场玩家会互相抵消的游戏。在物理学中，它描述了费米子（Fermions，如电子，它们讨厌处于同一位置）。
• 永恒式（Permanent，即“社交”得分）： 这与行列式类似，但你永远不会减去任何项。你只是把所有东西都加起来。这就像一场无论玩家是谁都会获得积分的游戏。在物理学中，它描述了玻色子（Bosons，如光子，它们喜欢聚集在一起）。
• 不变式（Immanant，即“混合”得分）： 这是本文的研究重点。它是两者之间的中间地带。想象一个规则取决于粒子“个性”的游戏。有些粒子表现得像“反社交”型，有些表现得像“社交”型，而有些则是两者的混合。不变式是使用这些混合规则计算出的得分。论文研究了每一种可能的“个性”（在数学上称为 $n$ 的分拆），以观察这种得分的表现如何。

2. 主要发现：平均得分

作者想要知道：如果我从一个巨大的 $d \times d$ 网格中随机选取一个 $n \times n$ 的部分，这个不变式得分平方的平均大小是多少？

他们发现了一个优美且简单的规则：
平均大小完全取决于两个“规模”（维度）的比率：

1. 对于 $n$ 个粒子，该“个性”（不变式规则）可以排列出的方式数量。
2. 在巨大的 $d$ 维宇宙中，同一种“个性”可以排列出的方式数量。

类比：
想象你有一个特定的舞蹈动作（不变式规则）。

• 第一个数字是你在一个小房间里完美完成那个动作需要多少名舞者（$n$）。
• 第二个数字是你在一个巨大的体育场里完成那个动作需要多少名舞者（$d$）。
  论文证明了，在体育场中这场舞蹈的平均“响度”（平方得分）仅仅是小房间的容量与体育场针对该特定舞蹈的容量之比。

他们还发现，对于非常大的体育场（大 $d$），平均响度的下降是非常可预测的，大约呈 $1/d^n$ 的趋势。

3. 得分的“等级制度”

论文还研究了哪些“个性”规则会产生更响亮或更安静的得分。他们发现了一种“等级制度”（称为支配序 order）：

• 某些规则（如“社交”永恒式）往往会产生较大的平均得分。
• 其他规则（如“反社交”行列式）往往会产生较小的平均得分。
• “混合”规则则介于两者之间，具体取决于它们是如何混合的。

你可以把它想象成房间里不同类型的噪音。有些类型的噪音（永恒式）天生比其他类型（行列式）更响，而论文精确地描绘了它们到底有多响。

4. 难点所在：“二阶矩”（方差）

计算得分的平均值是容易的部分（“一阶矩”）。论文还尝试计算二阶矩，这相当于在问：“得分的波动程度如何？得分是始终接近平均值，还是有时会变得非常剧烈？”

这要困难得多。这不仅是在预测人群的平均身高，还在预测每个人之间身高的差异。

• 对于“反社交”（行列式）和“社交”（永恒式）的情况，作者找到了特定的公式。
• 对于“混合”情况（不变式），数学计算变得极其复杂。作者不得不编写计算机程序来处理小规模群体（最多 5 个粒子）的数据。
• 他们发现，虽然这些公式是复杂的有理多项式（含有 $d$ 的分式），但它们是可以计算的。他们甚至为多达 9 个粒子的群体找到了“主导项”（leading term，即答案中最重要的部分）的公式。

5. 为什么这很重要？（根据论文所述）

论文提到，这些计算对于理解计算复杂度非常有用。

• 简单来说：如果你试图构建一台能够模拟这些量子粒子的计算机，了解这些得分的“平均值”和“波动”有助于证明，对于随机输入，该计算机需要极其庞大的时间才能解决问题。
• 这表明，对于某些类型的粒子（具有“混合”对称性的粒子），该问题与著名的“玻色子采样”（BosonSampling）问题一样困难（或者说在特定意义上一样难），而后者是已知经典计算机极难解决的问题。

总结

这篇论文是一张数学地图。它告诉我们，如果你从一个随机的量子宇宙切片中提取一个特定的“混合”得分（不变式）：

1. 平均值： 你可以使用维度的简单比例来预测这个得分的大小。
2. 层级： 一些“混合”规则天生比其他规则更响亮。
3. 波动： 虽然计算精确的波动非常困难，但作者已经提供了工具（以及计算机生成的结果）来计算它（针对小规模粒子群）。

他们通过使用一种被称为“Weingarten 微积分”（Weingarten Calculus）的强大数学工具箱来实现这一点，这种工具箱充当了专门的计算器，用于对所有可能的量子系统随机洗牌进行平均化处理。

技术摘要

技术摘要：$S_n$ 的混合对称性：$U(d)$ 子矩阵采样中的不变式 (Immanants)

问题陈述
本文研究了从 $U(d)$ 中的 Haar 分布酉矩阵中抽取的 $n \times n$ 子矩阵的不变式（immanants）的统计性质，其中 $n \le d$。虽然不可分辨玻色子和费米子的量子态分别对应于置换式（permanent）和行列式（determinant），但部分可分辨粒子的系统可能表现出混合置换对称性。这些状态在对称群 $S_n$ 的不可约表示（irreps）下进行变换，而这些表示既不是完全对称的，也不是完全反对称的。作者研究了这些不变式的模平方 $|\text{Imm}_\lambda M|^2$ 的矩，以了解其分布及其（反）集中性质。此类分析的动机在于，为建立采样这些矩阵函数的平均情况计算复杂度奠定基础，这是证明量子计算优势的关键组成部分。

方法论
本文采用的主要数学工具是 Weingarten 微积分 (Weingarten Calculus)，这是一个用于对酉群上关于 Haar 测度的矩阵元多项式进行积分的框架。

1. 一阶矩（均值）： 作者通过展开不变式的定义并应用矩阵元的二阶矩（$m=n$）Weingarten 公式，推导出了 $|\text{Imm}_\lambda M|^2$ 的均值。这使得积分简化为对置换的求和，并利用有限群特征标的正交关系进行了简化。
2. 二阶矩： 计算矩阵元的四阶矩（$m=2n$）以求得 $|\text{Imm}_\lambda M|^4$ 的均值要复杂得多。作者引入了特定的 $S_{2n}$ 子群：
   • $V_n$：一个置换 $n \times 2$ 阵列中列内符号的子群（同构于 $S_n \times S_n$）。
   • $H_n$：一个交换行符号的子群（同构于 $\mathbb{Z}_2^n$）。
     通过利用这些子群上特征标和的对称性，作者降低了计算求和的复杂度。
3. 渐近分析： 提取矩的领先阶项，以确定当 $d \to \infty$ 时的行为。

主要贡献与结果

• 均值的精确公式： 本文建立了平方不变式均值的闭合形式表达式：
  $$\int_{U(d)} dU \, |\text{Imm}_\lambda M|^2 = \frac{n!}{N^\lambda(d)}$$
  其中 $N^\lambda(d)$ 是由由分划 $\lambda$ 标记的 $U(d)$ 表示的维数公式导出的 $d$ 的多项式。该结果推广了已知的行列式和置换式结果（重现了 Nezami 的发现）。

  • 支配序 (Dominance Order)： 作者证明，如果分划 $\lambda$ 被 $\mu$ 所支配（$\lambda \triangleleft \mu$），则对于固定的 $d$，$|\text{Imm}_\lambda M|^2$ 的均值严格大于 $|\text{Imm}_\mu M|^2$ 的均值。

• 二阶矩的算法公式： 虽然没有提供任意 $\lambda$ 的四阶矩的一般闭合形式表达式，但作者推导出了一个算法公式（命题 6.3），该公式利用子群 $H_n$ 和 $V_n$ 的对称性来减少评估所需的项数。

  • 显式求值： 利用该算法，作者为所有满足 $n \le 5$ 的分划 $\lambda \vdash n$ 提供了二阶矩的显式有理多项式表达式。
  • 特殊情况： 对于行列式（$\lambda=(1^n)$），推导出了闭合形式：$\int |\text{Det } M|^4 = 1/\text{dim}((2n), U(d))$。对于置换式（$\lambda=(n)$），基于已推导出的结构提出了一个猜想。

• 领先项分析： 作者推导出了四阶矩展开式中 $1/d$ 次幂的领先系数 $J_\lambda$ 的公式。该系数被证明对于共轭分划具有对称性（$J_\lambda = J_{\lambda'}$）。针对 $n \le 9$ 的 $J_\lambda$ 进行了显式数值计算。

• 数值验证： 作者通过对 Haar 随机酉矩阵进行数值模拟验证了理论预测，结果显示推导出的有理多项式与来自 $10^4$ 到 $10^5$ 个子矩阵的平均数据高度吻合。

意义与主张
本文声称提供了对随机酉系综中混合对称态不变式矩的首次系统性处理。其重要性在于：

1. 理论基础： 提供了关于一阶和二阶矩的显式 $d$ 相关公式，这些公式对于分析这些函数的集中性质是必要的。
2. 复杂度含义： 作者指出，理解这些矩是证明采样不变式（这与 BosonSampling 和量子计算优势的广泛背景相关）的平均情况硬度结果的前提条件。
3. 计算限制： 本工作强调了高阶矩计算需求的快速增长，这使得显式多项式结果仅限于 $n \le 5$，而领先项分析则扩展到了 $n \le 9$。

作者明确指出，结果的完整证明已留待未来发表，本文呈现的是作为 ISQS29 报告内容的总结性结果与算法。