群表示的矩阵元与重数

在 Shor 算法 中我们已经看到，循环群上的量子傅里叶变换（QFT）能把”周期”这种隐藏结构转化为可测量的频率。本词条把同一思想推广到一般群：任意有限群（以及 $U(d)$ 等紧群的多项式表示）上的 QFT，会把最容易实现的”群元素左乘”操作，自动分解成各个不可约表示的直和。于是，一个经典计算机连存储都做不到的指数大酉矩阵，其单个矩阵元却可以被量子电路高效估计。

这个能力有什么用？表示论是处理对称性的通用语言：对称群 $S_n$ 的不可约表示刻画 $n$ 体系统的置换对称性，$U(d)$ 的表示刻画 $n$ 个 $d$ 维系统的集体旋转对称性。表示的矩阵元与各种重数（Kronecker 系数、Littlewood–Richardson 系数、Kostka 数等）是代数组合学、量子多体物理乃至几何复杂性理论中的基本对象。2008 年 Jordan 系统提出了”用量子算法估计不可约表示矩阵元”的框架（Zoo 编号 106）；其技术基础——对称群的高效 QFT——早在 1997 年就由 Beals 给出（Zoo 编号 196），而 $U(d)$ 一侧对应的 Schur 变换则由 Bacon、Chuang 与 Harrow 在 2006 年构造（Zoo 编号 197）。近年来这一思路被进一步推向表示重数的计算（Zoo 编号 460、516），但 2025 年 Panova 的经典算法突破（Zoo 编号 515）又大幅收窄了量子优势的边界。本词条的目标是把这条线的数学机制讲清楚：群 QFT 为什么产生不可约块、矩阵元如何经干涉读出、重数如何变成投影算子的秩，以及哪些量真的能高效算、哪些不能。

读者需要的前置知识：量子傅里叶变换与相位估计、振幅放大与振幅估计的基本结论（Grover 算法一章）、以及群论的基本概念（群、同态、共轭类）。表示论本身从零讲起。

1. 计算任务是什么

1.1 表示与不可约表示

定义（酉表示）。设 $G$ 是一个群，$V$ 是有限维复内积空间。$G$ 在 $V$ 上的酉表示 (unitary representation) 是一个群同态

$$\rho :G\to U(V),\rho (gh)=\rho (g)\rho (h),$$

其中 $U(V)$ 是 $V$ 上全体酉算子构成的群。也就是说，每个抽象群元素 $g$ 被替换成一个具体的酉矩阵 $\rho (g)$，并且”先乘 $h$ 再乘 $g$“在矩阵一侧忠实复现。同态条件蕴含两个常用推论：$\rho (e)=I$（单位元映到恒等），以及 $\rho (g^{-1})=\rho (g{)}^{-1}=\rho (g{)}^{†}$（酉矩阵的逆等于共轭转置）。

例。任何群都有平凡表示：$V=\mathbb{C}$，$\rho (g)=1$ 对所有 $g$ 成立。对称群 $S_n$ 还有符号表示：$\rho (\sigma )=\mathrm{sgn}(\sigma )=\pm 1$，按置换的奇偶性取值。这两个表示都是一维的。

定义（不可约表示）。若子空间 $W\subseteq V$ 满足 $\rho (g)W\subseteq W$ 对所有 $g\in G$ 成立，称 $W$ 为不变子空间。若 $V$ 除了 $\{0\}$ 和 $V$ 自身之外没有别的不变子空间，称 $\rho$ 不可约 (irreducible)。

不可约表示之于一般表示，正如素数之于整数：有限群的任何酉表示都可以分解为不可约表示的直和（完全可约性）。因此理解一个群的所有表示，归结为理解它的全部不可约表示。我们把 $G$ 的两两不等价的不可约表示的集合记作 $\hat{G}$，用标签 $\lambda \in \hat{G}$ 索引，对应表示空间 $V_{\lambda }$、维数 $d_{\lambda }=\dim V_{\lambda }$、表示矩阵 ${\rho }_{\lambda }(g)$。

1.2 任务陈述：估计单个矩阵元

现在可以陈述本词条的核心计算任务了。

矩阵元问题。给定群 $G$、不可约表示标签 $\lambda \in \hat{G}$、群元素 $g$、基向量标签 $i,j\in \{1,\dots ,d_{\lambda }\}$ 以及精度 $ϵ>0$，输出一个复数 $\tilde{\rho }$，使得以高概率

$$|\tilde{\rho }-{\rho }_{\lambda }(g{)}_{ij}|\le ϵ,\text{其中}{\rho }_{\lambda }(g{)}_{ij}=⟨i|{\rho }_{\lambda }(g)|j⟩$$

是 ${\rho }_{\lambda }(g)$ 在选定基下的第 $(i,j)$ 个矩阵元。

请特别注意输出的规模：答案只是一个复数，而不是整张 $d_{\lambda }\times d_{\lambda }$ 矩阵。这一区分是全部量子优势的来源。一个算法可以关于 $\log d_{\lambda }$ 多项式运行，即使 $d_{\lambda }$ 本身指数大——这与相位估计”读出酉矩阵的某个相位”而不必写下整个酉矩阵是完全相同的精神。

1.3 经典算法的瓶颈在哪里

经典算法处理表示论对象时，通常的做法是把表示矩阵显式构造出来，再做线性代数运算。这条路在指数维表示面前直接失效，原因分三层：

• 存储：当 $G=S_n$ 时，不可约表示的维数 $d_{\lambda }$ 可以大到 $n!$ 的平方根量级（$S_n$ 有 $n!$ 个元素，维数平方和为 $n!$，见第 2.1 节）。一张 $d_{\lambda }\times d_{\lambda }$ 的矩阵有 $d_{\lambda }^2$ 个复数元，连写下来都不可能，遑论乘法。
• 构造：即便只想算一个矩阵元，经典的组合算法（例如沿 Young 表的递推规则）需要在表示空间的基上逐层展开，基的大小本身就是 $d_{\lambda }$。
• 重数：Kronecker 系数等重数涉及三个指数维表示的分解，已知的经典算法全部需要超多项式时间；事实上这些量被普遍认为不存在多项式时间的经典算法（详见第 4.5 节的讨论与保留条款）。

经典计算机并非对所有相关问题都无能为力——例如 $S_n$ 的角色（表示矩阵的迹）有高效的组合规则可算。本词条的论点是：量子计算把可高效触及的范围从”迹”扩大到了”单个矩阵元”和”带归一化的重数”，而这个扩大恰好落在”输出规模小、中间对象指数大”的甜区上。

2. 群 QFT 为何产生不可约表示块

本节完成全课的核心推导：证明群 QFT 把”左乘 $g$“这一平凡操作变成不可约表示的直和。整个推导分四步：定义 QFT、引入正交关系、逐步计算共轭作用、用干涉电路读出矩阵元。

2.1 群上的量子傅里叶变换

设 $G$ 是有限群。取一个 $|G|$ 维的希尔伯特空间，以群元素标记计算基矢 $\{|x⟩{\}}_{x\in G}$。$G$ 上的量子傅里叶变换是如下酉变换：

$$F_G|x⟩=\sum _{\lambda \in \hat{G}}\sqrt{\frac{d_{\lambda }}{|G|}}\sum _{i,j=1}^{d_{\lambda }}{\rho }_{\lambda }(x{)}_{ij}|\lambda ,i,j⟩.$$

先检查两边维数一致。右边三元组 $(\lambda ,i,j)$ 的总数是 ${\sum }_{\lambda }{d}_{\lambda }^2$。我们断言

$$\sum _{\lambda \in \hat{G}}{d}_{\lambda }^2=|G|,$$

这保证右边的基底恰好也是 $|G|$ 个。这个恒等式有一个干净的角色论推导。考虑正则表示：$G$ 作用在自身的计算基上，${\rho }_{\mathrm{reg}}(g)|x⟩=|gx⟩$。其角色（迹）好算：矩阵 ${\rho }_{\mathrm{reg}}(g)$ 是对换基矢的置换矩阵，迹等于不动点数，而 $gx=x$ 蕴含 $g=e$，故

$${\chi }_{\mathrm{reg}}(g)=\{\begin{array}{ll}|G|,& g=e,\\ 0,& g\ne e.\end{array}$$

另一方面，任何表示分解为不可约表示时，$\lambda$ 出现的重数等于角色内积 $\frac{1}{|G|}{\sum }_g{\chi }_{\mathrm{reg}}(g{)}^{\ast }{\chi }_{\lambda }(g)$（角色正交性，见 2.2 节）；代入上式，只有 $g=e$ 一项非零，得到重数 $=\frac{1}{|G|}\cdot |G|\cdot {\chi }_{\lambda }(e)=d_{\lambda }$。即正则表示含每个不可约表示各 $d_{\lambda }$ 份，比较维数即得 $|G|={\sum }_{\lambda }{d}_{\lambda }^2$。Q.E.D.

这个计算还透露了 QFT 输出的结构：标签 $(\lambda ,i,j)$ 中，$\lambda$ 是不可约表示，$i$ 是表示空间内部的行指标，而 $j$ 是”重数指标”——$V_{\lambda }$ 在正则表示中出现 $d_{\lambda }$ 次，用 $j$ 编号。$F_G$ 正是把”群元素基”换成”不可约块基”的换基酉矩阵，其酉性由下一小节的正交关系保证（$F_G$ 的列正是不可约矩阵元函数 ${\rho }_{\lambda }(\cdot {)}_{ij}$，它们在群上的内积由 Schur 正交关系归一）。

2.2 关键工具：Schur 正交关系

定理（Schur 正交关系）。设 $\lambda ,\mu \in \hat{G}$，则对任意指标 $i,j,k,l$，

$$\sum _{g\in G}{\rho }_{\lambda }(g{)}_{ij}^{\ast }{\rho }_{\mu }(g{)}_{kl}=\frac{|G|}{d_{\lambda }}{\delta }_{\lambda \mu }{\delta }_{ik}{\delta }_{jl}.$$

证明梗概（标准论证，值得记住骨架）。固定 $j,l$，定义算子 $T={\sum }_{g\in G}{\rho }_{\mu }(g)|k⟩⟨j|{\rho }_{\lambda }(g^{-1})$。用同态性质可验证 $T$ 与群作用交换：${\rho }_{\mu }(h)T=T{\rho }_{\lambda }(h)$ 对所有 $h$ 成立（把求和变量 $g$ 换为 $hg$，群上求和平移不变）。这类算子称为交结算子 (intertwiner)。Schur 引理断言：两个不可约表示之间的交结算子，若两表示不等价则必为零，若等价则必为恒等的标量倍。于是 $T=c{\delta }_{\lambda \mu }I$；取迹定出标量 $c$，即得上式。把 ${\rho }_{\lambda }(g^{-1})={\rho }_{\lambda }(g{)}^{†}$ 展开成分量就是定理中的形式。Q.E.D.

取 $i=j$、$k=l$ 并对 $i,k$ 求和，迹 ${\sum }_i{\rho }_{\lambda }(g{)}_{ii}={\chi }_{\lambda }(g)$ 是角色 (character)，于是得到更常用的角色正交关系

$$\frac{1}{|G|}\sum _{g\in G}{\chi }_{\lambda }(g{)}^{\ast }{\chi }_{\mu }(g)={\delta }_{\lambda \mu }.$$

它的含义是：每个不可约表示的角色是”类函数空间”（在共轭类上取常值的函数）中的单位向量，且不同不可约表示的角色互相正交。2.1 节算重数时用的就是这个内积。第 4 节构造投影算子时，我们还会再用一次。

2.3 块对角化：逐步推导

定义左乘酉算子

$$L_g|x⟩=|gx⟩.$$

它在群元素基下只是一个置换矩阵，电路实现容易（群乘法本身通常是可高效计算的经典函数，做成可逆电路即可）。本节的中心命题是：

$$\boxed{F_G{L}_g{F}_G^{†}=\underset{\lambda \in \hat{G}}{⨁}{\rho }_{\lambda }(g)\otimes I_{d_{\lambda }}}$$

即：在 QFT 基下，左乘 $g$ 在每个 $\lambda$ 扇区里就是”在表示空间指标上作用 ${\rho }_{\lambda }(g)$、在重数指标上什么也不做”。（具体由共轭或转置出现在哪个指标上，取决于 QFT 的符号约定；我们这里固定上面的约定并把账算到底，物理结论与约定无关。）

逐步验证。我们把这个算子作用在任意 QFT 基矢 $|\lambda ,i,j⟩$ 上，分三步。

第一步，作用 $F_G^{†}$。由 $F_G$ 的定义，$⟨\lambda ,i,j|F_G|x⟩=\sqrt{d_{\lambda }/|G|}{\rho }_{\lambda }(x{)}_{ij}$，取共轭转置得

$$F_G^{†}|\lambda ,i,j⟩=\sqrt{\frac{d_{\lambda }}{|G|}}\sum _{x\in G}{\rho }_{\lambda }(x{)}_{ij}^{\ast }|x⟩.$$

第二步，作用 $L_g$ 把 $|x⟩$ 变成 $|gx⟩$，再把求和变量换为 $y=gx$（即 $x=g^{-1}y$；群上求和允许这样的平移）：

$$L_g{F}_G^{†}|\lambda ,i,j⟩=\sqrt{\frac{d_{\lambda }}{|G|}}\sum _{y\in G}{\rho }_{\lambda }(g^{-1}y{)}_{ij}^{\ast }|y⟩.$$

第三步，作用 $F_G$。按定义展开 $F_G|y⟩$：

$$F_G{L}_g{F}_G^{†}|\lambda ,i,j⟩=\sum _{\mu \in \hat{G}}\frac{\sqrt{d_{\lambda }{d}_{\mu }}}{|G|}\sum _{a,b=1}^{d_{\mu }}[\sum _{y\in G}{\rho }_{\lambda }(g^{-1}y{)}_{ij}^{\ast }{\rho }_{\mu }(y{)}_{ab}]|\mu ,a,b⟩.$$

现在处理方括号里的群求和，这是整个推导的关键一步。先用同态性质把 ${\rho }_{\lambda }(g^{-1}y)$ 拆开：${\rho }_{\lambda }(g^{-1}y{)}_{ij}={\sum }_c{\rho }_{\lambda }(g^{-1}{)}_{ic}{\rho }_{\lambda }(y{)}_{cj}$，取复共轭后代入：

$$\sum _{y\in G}{\rho }_{\lambda }(g^{-1}y{)}_{ij}^{\ast }{\rho }_{\mu }(y{)}_{ab}=\sum _c{\rho }_{\lambda }(g^{-1}{)}_{ic}^{\ast }[\sum _{y\in G}{\rho }_{\lambda }(y{)}_{cj}^{\ast }{\rho }_{\mu }(y{)}_{ab}].$$

内层求和正好是 Schur 正交关系（2.2 节，指标对应 $c,j$ 对 $a,b$）：

$$\sum _{y\in G}{\rho }_{\lambda }(y{)}_{cj}^{\ast }{\rho }_{\mu }(y{)}_{ab}=\frac{|G|}{d_{\lambda }}{\delta }_{\lambda \mu }{\delta }_{ca}{\delta }_{jb}.$$

三个 Kronecker $\delta$ 的效应：(i) ${\delta }_{\lambda \mu }$ 把外层 $\mu$ 求和钉死在 $\mu =\lambda$——不同不可约扇区之间没有泄漏，这就是”块对角”的来源；(ii) ${\delta }_{ca}$ 把 $c$ 求和钉死在 $c=a$；(iii) ${\delta }_{jb}$ 把输出基矢的重数指标钉死在 $b=j$——重数指标原封不动，这就是张量积中 $I_{d_{\lambda }}$ 因子的来源。代回并化简系数：

$$\frac{\sqrt{d_{\lambda }{d}_{\mu }}}{|G|}\cdot \frac{|G|}{d_{\lambda }}{|}_{\mu =\lambda }=1,$$

于是

$$F_G{L}_g{F}_G^{†}|\lambda ,i,j⟩=\sum _a{\rho }_{\lambda }(g^{-1}{)}_{ia}^{\ast }|\lambda ,a,j⟩=\sum _a{\rho }_{\lambda }(g{)}_{ai}|\lambda ,a,j⟩,$$

最后一步用了酉性：${\rho }_{\lambda }(g^{-1}{)}_{ia}^{\ast }=({\rho }_{\lambda }(g{)}^{-1}{)}_{ia}^{\ast }=({\rho }_{\lambda }(g{)}^{†}{)}_{ia}^{\ast }={\rho }_{\lambda }(g{)}_{ai}$。结果正是在 $i$ 指标上作用矩阵 ${\rho }_{\lambda }(g)$、在 $j$ 指标上作用恒等，即 ${⨁}_{\lambda }{\rho }_{\lambda }(g)\otimes I_{d_{\lambda }}$。Q.E.D.

物理意义。“左乘 $g$“原本只是在 $|G|$ 维空间里置换基矢，毫无表示论色彩；但经过 QFT 换基，它自动在每个表示标签区执行目标不可约矩阵 ${\rho }_{\lambda }(g)$。换句话说：QFT 是一个”编译器”，把廉价的群运算编译成昂贵的表示矩阵。只要 $F_G$、$F_G^{†}$ 和 $L_g$ 都有多项式大小的电路，我们就能在 $\log d_{\lambda }$ 量级的有效维度上作用 ${\rho }_{\lambda }(g)$，而从不显式生成它。

2.4 Hadamard 测试：读出单个矩阵元

有了受控的块酉 $W=F_G{L}_g{F}_G^{†}$，读矩阵元就是标准的 Hadamard 测试（与相位估计一章的干涉测量同源）。目标是估计 ${\rho }_{\lambda }(g{)}_{ij}=⟨\lambda ,i,k|W|\lambda ,j,k⟩$——注意重数指标 $k$ 取任意固定值均可，因为块结构在 $k$ 上是恒等。

电路：一个控制比特（寄存器 1）置于 $|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$，主寄存器（寄存器 2）制备为 $|\lambda ,j,k⟩$；施加受控-$W$（控制比特为 $|1⟩$ 时作用 $W$）。记 $P=|\lambda ,i,k⟩⟨\lambda ,i,k|$ 为目标基矢上的投影。末态为

$$|\Psi ⟩=\frac{1}{\sqrt{2}}(|0⟩|\lambda ,j,k⟩+|1⟩W|\lambda ,j,k⟩).$$

我们测量联合可观测量 $X\otimes P$（即：在主寄存器上投影到 $|\lambda ,i,k⟩$，同时读控制比特的 $X$）：

$$⟨\Psi |X\otimes P|\Psi ⟩=\frac{1}{2}(⟨\lambda ,j,k|PW|\lambda ,j,k⟩+⟨\lambda ,j,k|W^{†}P|\lambda ,j,k⟩).$$

展开交叉项时用了 $X|0⟩=|1⟩$、$X|1⟩=|0⟩$，所以只有控制比特翻转的交叉项有贡献。由于 $P$ 是到单基矢的投影，$PW|\lambda ,j,k⟩={\rho }_{\lambda }(g{)}_{ij}|\lambda ,i,k⟩$，于是

$$⟨\Psi |X\otimes P|\Psi ⟩=\frac{1}{2}({\rho }_{\lambda }(g{)}_{ij}+{\rho }_{\lambda }(g{)}_{ij}^{\ast })=\mathrm{Re}{\rho }_{\lambda }(g{)}_{ij}.$$

同理，把 $X$ 换成 $Y$（$Y|0⟩=i|1⟩$、$Y|1⟩=-i|0⟩$，交叉项多出一个 $\pm i$），得到

$$⟨\Psi |Y\otimes P|\Psi ⟩=\mathrm{Im}{\rho }_{\lambda }(g{)}_{ij}.$$

实部和虚部分别由控制比特的 $X$、$Y$ 期望给出——这就是”测量控制比特读出矩阵元”的精确含义。

2.5 复杂度分析

采样法。可观测量 $X\otimes P$ 的本征值落在 $\{-1,0,1\}$ 内，是有界量。每次实验得到一个样本，样本均值依 Hoeffding 不等式以 $O(1/\sqrt{T})$ 的速度收敛到真期望（$T$ 为实验次数）：要把加性误差压到 $ϵ$，需要 $T=O(1/{ϵ}^2)$ 次重复。每次重复的电路代价是一次受控-$W$，即两次群 QFT 加一次左乘；当 $G=S_n$ 时这些都是关于 $n$ 的多项式（见第 3 节）。因此单个矩阵元的加性 $ϵ$ 估计总代价是关于 $\log |G|$ 与 $1/ϵ$ 的多项式。

振幅估计法。如果允许相干地反复调用整块电路（相干访问模型），“估计一个干涉条纹的期望值”是振幅估计的标准任务，可把精度—代价关系从 $O(1/{ϵ}^2)$ 改善到 $O(1/ϵ)$，与 Grover 搜索相对经典采样的平方加速同源。代价是电路深度按 $1/ϵ$ 增长，且需要保持相干。

两种模式都不需要输出那张指数大的矩阵——电路宽度始终只有 $O(\log |G|)$ 个量子比特。

3. 对称群与 Schur 变换

上一节是抽象框架。要让它落地，必须对具体的群回答一个问题：$F_G$ 本身有没有多项式大小的量子电路？ 对 $S_n$ 答案是肯定的（Beals），对 $U(d)$ 一侧对应的工具是 Schur 变换。

3.1 对称群的不可约表示

对称群 $S_n$ 的不可约表示由 $n$ 的整数分拆 (partition)

$$\lambda ⊢n,\lambda =({\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{\ell }>0),{\lambda }_1+\cdots +{\lambda }_{\ell }=n$$

标记。每个分拆画成一个 Young 图（第 $r$ 行 ${\lambda }_r$ 个方格的左对齐图形），表示空间 $V_{\lambda }$ 的一组标准基由标准 Young 表（把 $1,\dots ,n$ 填入 Young 图，使每行每列严格递增）编号，因此 $d_{\lambda }$ 等于形状 $\lambda$ 的标准 Young 表个数（有 hook-length 公式可算）。关键点：分拆数和标准 Young 表都可以高效地枚举、编码，$|\lambda ,i,j⟩$ 中的每个标签都有多项式比特长度的组合编码——这是”多项式电路”得以谈论的前提。

3.2 Beals 的对称群 QFT

Beals（Zoo 编号 196，STOC 1997）给出了 $S_n$ 上 QFT 的高效量子电路，线路规模关于 $n$ 为多项式。构造的思想是把 $S_n$ 的 QFT 沿着子群塔 $S_1\subset S_2\subset \cdots \subset S_n$ 逐层分解，每层利用”限制表示按去掉一个方格的 Young 图分裂”的分支规则 (branching rule) 做受控旋转——这与我们在 QFT 一章看到的”按比特逐级分解”的精神一致，只是把 ${\mathbb{Z}}_{2^n}$ 的逐级结构换成了对称群的子群塔。结合第 2 节：

推论。任意 $S_n$ 不可约表示的单个矩阵元，可以在关于 $n$ 与 $1/ϵ$ 的多项式时间内以加性误差 $ϵ$ 估计。这里的输入是 $(\lambda ,\sigma ,i,j)$，全部用多项式比特编码；$d_{\lambda }$ 指数大并不构成障碍。

3.3 Schur–Weyl 对偶与 Schur 变换

连续群不能照搬有限群 QFT，但量子信息里最常用的连续对称性——$n$ 个 $d$ 维系统的集体酉旋转 $U^{\otimes n}$——有一套平行的理论。

在 $({\mathbb{C}}^d{)}^{\otimes n}$ 上有两个天然的作用：

• $U(d)$ 按”集体旋转”作用：$U\mapsto U^{\otimes n}$；
• $S_n$ 按”置换张量因子”作用：$\sigma \mapsto P_{\sigma }$，$P_{\sigma }|v_1⟩\otimes \cdots \otimes |v_n⟩=|v_{{\sigma }^{-1}(1)}⟩\otimes \cdots \otimes |v_{{\sigma }^{-1}(n)}⟩$。

这两个作用互相交换（先旋转再置换，等于先置换再旋转，因为每个张量因子受的旋转相同）。Schur–Weyl 对偶断言，不仅如此，它们还互为对方在这个空间里的全部对称：整个空间分解为

$$({\mathbb{C}}^d{)}^{\otimes n}\cong \underset{\begin{array}{c}\lambda ⊢n\\ \ell (\lambda )\le d\end{array}}{⨁}{Q}_{\lambda }^d\otimes P_{\lambda },$$

其中 $Q_{\lambda }^d$ 承载 $U(d)$ 的不可约表示，$P_{\lambda }$ 承载 $S_n$ 的不可约表示，分拆 $\lambda$ 同时标记两者，$\ell (\lambda )$ 是 $\lambda$ 的行数（超过 $d$ 行的分拆不出现）。直觉上：$U^{\otimes n}$ 和置换共同的对称类型，恰好由一个 Young 图完整刻画。

维数小检查（$n=2$，任意 $d$）。两个张量因子只有两种置换对称性：对称与反对称，

$$({\mathbb{C}}^d{)}^{\otimes 2}=\underset{\lambda =(2)}{\underbrace{{\mathrm{Sym}}^2}}\oplus \underset{\lambda =(1,1)}{\underbrace{{\wedge }^2}},\frac{d(d+1)}{2}+\frac{d(d-1)}{2}=d^2,$$

其中 ${\mathrm{Sym}}^2=Q_{(2)}^d$ 乘 $S_2$ 的平凡表示（$d_{(2)}=1$），${\wedge }^2=Q_{(1,1)}^d$ 乘符号表示（$d_{(1,1)}=1$）。维数恰好闭合。

Schur 变换 $U_{\mathrm{Sch}}$ 就是显式完成这个换基的酉矩阵：把”张量积基”换成”$|\lambda ,q,p⟩$ 基”（$q$ 为 $Q_{\lambda }^d$ 的指标，$p$ 为 $P_{\lambda }$ 的指标）。Bacon、Chuang 与 Harrow（Zoo 编号 197）给出了关于 $n$、$\log d$ 和 $1/ϵ$ 多项式规模的 Schur 变换量子电路，方法同样是沿 $n$ 逐个加入张量因子、用 Clebsch–Gordan 型的受控旋转逐级耦合。

3.4 从 $U^{\otimes n}$ 到不可约块

Schur 变换与第 2 节的群 QFT 扮演完全相同的”编译器”角色。在 Schur 基下，物理上自然的集体旋转分解为

$$U_{\mathrm{Sch}}{U}^{\otimes n}{U}_{\mathrm{Sch}}^{†}=\underset{\lambda }{⨁}{Q}_{\lambda }^d(U)\otimes I_{d_{\lambda }},$$

即共轭 $U^{\otimes n}$ 后得到各 $Q_{\lambda }^d(U)$ 的块——$S_n$ 的重数空间 $P_{\lambda }$ 上同样只作用恒等。于是第 2.4 节的 Hadamard 测试原样适用：制备 Schur 基态、作用受控的 $U^{\otimes n}$、在目标 Schur 基矢上投影，即可估计 $U(d)$ 不可约表示的单个矩阵元。注意这里电路输入是 $d\times d$ 的 $U$（由 $\log d$ 个量子比特上的基本门实现），而 $Q_{\lambda }^d(U)$ 可以是指数维矩阵——$U^{\otimes n}$ 的”免费并行动力”被 Schur 变换兑换成了高维表示。

对多项式最高权的 $U(n)$、$SU(n)$、$SO(n)$ 表示，也可通过类似的分支规则构造多项式电路（Zoo 编号 106 处理的正是这一般情形）：沿子群链逐级限制表示，每层只做低维的受控旋转。我们不在此展开，但读者应记住模式：只要存在”逐级分解 + 每级低维”的结构，就有高效电路。

4. 从矩阵元到表示重数

矩阵元是”表示内部的坐标”；本词条的第二类目标是重数：某个不可约表示在一个大表示的分解中出现多少次。我们将看到，重数不是矩阵元，而是投影算子的秩——这决定了它能被量子算法以何种精度触及。

4.1 Kronecker 系数：一个具体实例

取 $S_n$ 的两个不可约表示 $V_{\lambda },V_{\mu }$，其张量积 $V_{\lambda }\otimes V_{\mu }$（$S_n$ 按对角方式 $g\mapsto {\rho }_{\lambda }(g)\otimes {\rho }_{\mu }(g)$ 作用）一般可约。Kronecker 系数 $g(\lambda ,\mu ,\nu )$ 是 $V_{\nu }$ 在其中的出现次数：

$$g(\lambda ,\mu ,\nu )=\dim {\mathrm{Hom}}_{S_n}(V_{\nu },V_{\lambda }\otimes V_{\mu }),$$

其中 ${\mathrm{Hom}}_{S_n}$ 表示与群作用交换的线性映射空间；其维数恰好数出”有多少种方式把 $V_{\nu }$ 嵌入张量积”，即重数。这类系数在代数组合与几何复杂性理论中是基本对象，且以难算著称。

4.2 等型投影算子：逐步推导

怎么把”数 $V_{\nu }$ 的份数”变成一个可测量的算子？答案是角色投影公式。

命题。设 $W$ 是有限群 $G$ 的任一酉表示（对我们来说 $W=V_{\lambda }\otimes V_{\mu }$，$G=S_n$），则算子

$${\Pi }_{\nu }=\frac{d_{\nu }}{|G|}\sum _{g\in G}{\chi }_{\nu }(g{)}^{\ast }{\rho }_W(g)$$

是投影到 $W$ 的 $\nu$-等型分量（$W$ 中所有同构于 $V_{\nu }$ 的子表示之和）的正交投影。

逐步验证。分三步。

第一步，${\Pi }_{\nu }$ 与群作用交换。对任意 $h\in G$，

$${\rho }_W(h){\Pi }_{\nu }{\rho }_W(h{)}^{-1}=\frac{d_{\nu }}{|G|}\sum _g{\chi }_{\nu }(g{)}^{\ast }{\rho }_W(hg{h}^{-1}),$$

把求和变量 $g$ 换为 $h^{-1}gh$（群上求和平移不变），并注意角色是类函数：${\chi }_{\nu }(h^{-1}gh)={\chi }_{\nu }(g)$，因为 ${\chi }_{\nu }(h^{-1}gh)=\mathrm{Tr}({\rho }_{\nu }(h{)}^{-1}{\rho }_{\nu }(g){\rho }_{\nu }(h))=\mathrm{Tr}{\rho }_{\nu }(g)$（迹的循环性）。于是右边等于 ${\Pi }_{\nu }$。

第二步，确定 ${\Pi }_{\nu }$ 在每个不可约子空间上的作用。把 $W$ 分解为不可约直和 $W={⨁}_{\sigma }{m}_{\sigma }{V}_{\sigma }$。由第一步与 Schur 引理，${\Pi }_{\nu }$ 在每个 $V_{\sigma }$ 上是标量 $c_{\sigma }I$。取该子空间上的迹定标量：一方面 ${\mathrm{Tr}}_{V_{\sigma }}({\Pi }_{\nu })=c_{\sigma }{d}_{\sigma }$；另一方面按定义

$${\mathrm{Tr}}_{V_{\sigma }}({\Pi }_{\nu })=\frac{d_{\nu }}{|G|}\sum _g{\chi }_{\nu }(g{)}^{\ast }{\chi }_{\sigma }(g)=d_{\nu }{\delta }_{\nu \sigma },$$

等号用了 2.2 节的角色正交关系。比较得 $c_{\sigma }={\delta }_{\nu \sigma }$：${\Pi }_{\nu }$ 在每个 $V_{\nu }$ 上是恒等、在其他不可约成分上是零。

第三步，合成。等型分量上的恒等、其余为零，正是到 $\nu$-等型分量的正交投影。Q.E.D.

4.3 秩与测量概率

秩的计算。投影的秩等于其像的维数。${\Pi }_{\nu }$ 的像是 $g(\lambda ,\mu ,\nu )$ 份 $V_{\nu }$ 的直和，每份贡献 $d_{\nu }$ 维，故

$$\mathrm{rank}({\Pi }_{\nu })=g(\lambda ,\mu ,\nu )d_{\nu }.$$

测量概率。量子 QFT（这里是 $S_n$ 的 QFT 或 Schur 变换）让我们在叠加中选择表示标签并测量投影 ${\Pi }_{\nu }$：制备态、施加投影测量 $\{{\Pi }_{\nu },I-{\Pi }_{\nu }\}$，结果 $\nu$ 被接受的概率携带秩的信息。最干净的方案是在 $V_{\lambda }\otimes V_{\mu }$ 的最大混合态 $\frac{I}{d_{\lambda }{d}_{\mu }}$ 上测量（制备方法：把重数/辅助寄存器置于最大混合态即可）。接受概率为

$$p_{\nu }=\mathrm{Tr}\left({\Pi }_{\nu }\frac{I}{d_{\lambda }{d}_{\mu }}\right)=\frac{\mathrm{rank}({\Pi }_{\nu })}{d_{\lambda }{d}_{\mu }}=\frac{g(\lambda ,\mu ,\nu )d_{\nu }}{d_{\lambda }{d}_{\mu }}.$$

逐步解读这个公式的每个因子：分子中的 $g(\lambda ,\mu ,\nu )$ 是重数（我们要的整数）、$d_{\nu }$ 是每份拷贝的维数；分母 $d_{\lambda }{d}_{\mu }$ 是张量积空间的总维数，来自最大混合态的归一化。因此量子算法天然输出的是归一化 Kronecker 系数 $g(\lambda ,\mu ,\nu )d_{\nu }/(d_{\lambda }{d}_{\mu })$ 的估计。

复杂度。用第 2.5 节同样的账：对 $p_{\nu }$ 做加性 $ϵ$ 估计，普通采样需 $O(1/{ϵ}^2)$ 次实验，振幅估计在相干模型下需 $O(1/ϵ)$ 次调用。每次实验的电路（$S_n$ QFT、投影测量的实现）关于 $n$ 为多项式。

4.4 保留条款：加性估计不等于精确计算

这里必须非常诚实地区分两件事。

• 可加性估计：当 $p_{\nu }$ 不太小（例如关于 $n$ 是多项式小的倒数），取 $ϵ$ 为同量级即可以多项式代价把 $p_{\nu }$ 估到有意义的相关精度。这正是 Larocca–Havlíček（Zoo 编号 516）框架的适用区间：他们把这种投影测量思路推广到 Kostka、Littlewood–Richardson、plethysm 与 Kronecker 重数，并明确要求相关表示维数比为多项式——等价地，要求 $p_{\nu }$ 至少为 $1/\mathrm{poly}(n)$。
• 不可逾越的障碍：若 $p_{\nu }$ 指数小，比如 $p_{\nu }=2^{-n}$，那么要把 $g(\lambda ,\mu ,\nu )$ 恢复为未归一化的整数（哪怕是判定它是 $0$ 还是 $1$），就需要 $ϵ<p_{\nu }/2$ 量级的加性精度，即 $\Omega (1/p_{\nu }^2)$（采样）或 $\Omega (1/p_{\nu })$（振幅估计）次实验——指数次。相对误差同理。

一句话：“可测投影”不等于”所有重数都能高效精确计算”。量子算法高效给出的是带维数归一化的加性估计；把它误读为”量子计算机多项式时间算出 Kronecker 系数”是常见错误。

4.5 量子优势的边界：2025 年的经典进展

量子算法能加性估计 $p_{\nu }$ 之后，接下来的问题是：同样的任务经典算法真的做不到吗？ Bravyi 等人（Zoo 编号 460）曾从量子一侧系统分析 Kronecker 系数的复杂性；而 Panova（Zoo 编号 515，2025 年）给出了许多同一参数区间上的经典多项式时间算法，推翻了部分文献中的超多项式加速猜想。现状可以概括为：

• 在若干参数族上，量子与经典都能多项式时间完成，现有结论只支持多项式级别的量子—经典差距；
• plethysm 等其余范围仍需逐项分析，不能笼统宣称指数加速。

这条时间线给学生的教训是普适的：引用量子优势结论时必须核对最新的经典算法进展，2024 年成立的”经典瓶颈”可能在 2025 年就不复存在。本词条保留条款的写法（“现有结论在若干族上只支持多项式差距”）正是这一现状的准确反映。

5. 小例子：$S_3$ 的标准表示

把全部机制在最小的非平凡例子 $S_3$ 上演算一遍。$S_3$ 有 $6$ 个元素，分三个共轭类：恒等 $e$（1 个）、对换 $(12),(13),(23)$（3 个）、三循环 $(123),(132)$（2 个）。

5.1 三个不可约表示与角色表

$S_3$ 恰有三个不可约表示，对应 $3$ 的三个分拆：

• 平凡表示 $V_{\mathrm{triv}}$（$\lambda =(3)$）：$d=1$，${\chi }_{\mathrm{triv}}(g)=1$；
• 符号表示 $V_{\mathrm{sign}}$（$\lambda =(1,1,1)$）：$d=1$，${\chi }_{\mathrm{sign}}(g)=\mathrm{sgn}(g)$，对换取 $-1$、三循环取 $1$；
• 标准表示 $V_{\mathrm{std}}$（$\lambda =(2,1)$）：$d=2$。

维数守恒检验：$1^2+1^2+2^2=6=|S_3|$，与 2.1 节的恒等式一致。

标准表示的角色可以用一个技巧手算。$S_3$ 在 ${\mathbb{C}}^3$ 上的置换表示（置换三个坐标轴）的角色等于不动点个数：$e$ 固定全部 3 个基矢，对换固定 1 个，三循环固定 0 个。而 ${\mathbb{C}}^3=V_{\mathrm{triv}}\oplus V_{\mathrm{std}}$（对角线方向是平凡子表示），角色相减：

$${\chi }_{\mathrm{std}}={\chi }_{\mathrm{perm}}-{\chi }_{\mathrm{triv}}:\begin{array}{cccc}& e& (\cdot \cdot )& (\cdot \cdot \cdot )\\ {\chi }_{\mathrm{perm}}& 3& 1& 0\\ {\chi }_{\mathrm{std}}& 2& 0& -1\end{array}$$

5.2 三循环的矩阵与矩阵元

把标准表示具体实现为平面 $V=\{(x_1,x_2,x_3)\in {\mathbb{C}}^3:x_1+x_2+x_3=0\}$ 上的坐标置换。三循环 $(123)$ 在这个平面上是旋转 $120^{\circ }$：它的阶是 3，而平面上阶为 3 的酉变换只能是 $\pm 120^{\circ }$ 旋转。取适当正交归一基，

$${\rho }_{\mathrm{std}}((123))=\left(\begin{array}{cc}-\frac{1}{2}& -\frac{\sqrt{3}}{2}\\ \frac{\sqrt{3}}{2}& -\frac{1}{2}\end{array}\right).$$

逐项验证这个矩阵与上面的一切相容：

• 角色：${\chi }_{\mathrm{std}}((123))=-\frac{1}{2}-\frac{1}{2}=-1$，与角色表一致；也等于 $2\cos 120^{\circ }=-1$（二维旋转的迹公式）。
• 阶：$\cos (3\cdot 120^{\circ })=\cos 360^{\circ }=1$，故 ${\rho }_{\mathrm{std}}((123){)}^3=I={\rho }_{\mathrm{std}}(e)$，同态要求满足。
• 矩阵元：例如 ${\rho }_{\mathrm{std}}((123){)}_{11}=-\frac{1}{2}$，${\rho }_{\mathrm{std}}((123){)}_{21}=\frac{\sqrt{3}}{2}$。

按第 2.4 节，QFT 块电路可用 Hadamard 干涉分别估计全部四个矩阵元：例如制备 $|\lambda =(2,1),j=1,k⟩$，作用受控的 $F_{S_3}{L}_{(123)}{F}_{S_3}^{†}$，在 $i=1$ 上投影并测控制比特 $X$，多次重复后样本均值收敛到 $-\frac{1}{2}$；测 $Y$ 得 $0$（该元为实数）。

5.3 张量平方的分解：完整计算

计算 $V_{\mathrm{std}}\otimes V_{\mathrm{std}}$ 的分解，即求 Kronecker 系数 $g(\mathrm{std},\mathrm{std},\nu )$。工具是角色论：张量积的角色是角色的乘积，${\chi }_{\mathrm{std}\otimes \mathrm{std}}(g)={\chi }_{\mathrm{std}}(g{)}^2$，再对角色做内积（2.2 节正交关系，注意共轭类的元素个数要加权：$e$ 类 1 个、对换类 3 个、三循环类 2 个）：

$${\chi }_{\mathrm{std}}^2:e\mapsto 4,(\cdot \cdot )\mapsto 0,(\cdot \cdot \cdot )\mapsto 1.$$

与三个不可约角色逐一内积：

$$\begin{array}{rl}⟨{\chi }_{\mathrm{std}}^2,{\chi }_{\mathrm{triv}}⟩& =\frac{1}{6}(1\cdot 4\cdot 1+3\cdot 0\cdot 1+2\cdot 1\cdot 1)=\frac{6}{6}=1,\\ ⟨{\chi }_{\mathrm{std}}^2,{\chi }_{\mathrm{sign}}⟩& =\frac{1}{6}(1\cdot 4\cdot 1+3\cdot 0\cdot (-1)+2\cdot 1\cdot 1)=1,\\ ⟨{\chi }_{\mathrm{std}}^2,{\chi }_{\mathrm{std}}⟩& =\frac{1}{6}(1\cdot 4\cdot 2+3\cdot 0\cdot 0+2\cdot 1\cdot (-1))=\frac{8-2}{6}=1.\end{array}$$

三个重数均为 1，即

$$V_{\mathrm{std}}\otimes V_{\mathrm{std}}\cong V_{\mathrm{triv}}\oplus V_{\mathrm{sign}}\oplus V_{\mathrm{std}}.$$

维数检查：$2\times 2=1+1+2$，正好闭合。

5.4 投影测量的数值

代入 4.3 节的公式，最大混合态（维数 $d_{\mathrm{std}}^2=4$）上三个投影的接受概率分别为

$$p_{\mathrm{triv}}=\frac{1\cdot 1}{4}=\frac{1}{4},p_{\mathrm{sign}}=\frac{1\cdot 1}{4}=\frac{1}{4},p_{\mathrm{std}}=\frac{1\cdot 2}{4}=\frac{1}{2}.$$

一致性检查：$p_{\mathrm{triv}}+p_{\mathrm{sign}}+p_{\mathrm{std}}=\frac{1}{4}+\frac{1}{4}+\frac{1}{2}=1$——三个投影构成完备测量，概率必然归一。秩检查：$\mathrm{rank}{\Pi }_{\mathrm{triv}}=1$、$\mathrm{rank}{\Pi }_{\mathrm{sign}}=1$、$\mathrm{rank}{\Pi }_{\mathrm{std}}=2$，合计 $4$，等于张量积空间维数。这个例子里 $p_{\nu }$ 都是常数，不存在第 4.4 节的指数小障碍；它展示的是”理想情形”的完整闭环。

6. 小结与习题

小结。

• 群 QFT 把左正则表示变为不可约表示的直和：$F_G{L}_g{F}_G^{†}={⨁}_{\lambda }{\rho }_{\lambda }(g)\otimes I_{d_{\lambda }}$，推导的引擎是 Schur 正交关系。
• Hadamard/振幅估计读取单个矩阵元，输出只是一个复数，不需要写出指数大的矩阵；加性 $ϵ$ 的代价为采样的 $O(1/{ϵ}^2)$ 或相干模型的 $O(1/ϵ)$。
• Schur 变换是 $U(d)$ 一侧的同一”编译器”：Schur–Weyl 对偶同时组织 $U(d)$ 与 $S_n$ 表示，共轭 $U^{\otimes n}$ 得到不可约块。
• 表示重数是投影算子的秩；高效可得的是带维数归一化的加性估计（如 $p_{\nu }=g(\lambda ,\mu ,\nu )d_{\nu }/(d_{\lambda }{d}_{\mu })$）。当 $p_{\nu }$ 指数小时，恢复整数重数仍需指数资源——“可测投影”不等于”高效精确计算”。
• 量子优势必须随经典算法进展更新：Panova 2025 的经典结果推翻了部分超多项式加速猜想，现有结论在若干族上只支持多项式量子—经典差距，不能沿用已被推翻的猜想。

习题。

1. 块对角化的另一半。2.3 节处理了左乘 $L_g|x⟩=|gx⟩$。定义右乘 $R_g|x⟩=|x{g}^{-1}⟩$，模仿三步推导计算 $F_G{R}_g{F}_G^{†}$ 在 $|\lambda ,i,j⟩$ 上的作用，说明它作用在哪个指标上、以何种转置/共轭形式出现，并由此解释块结构中 $I_{d_{\lambda }}$ 因子的来源。
2. Hadamard 测试的虚部。补全 2.4 节的计算：验证 $⟨\Psi |Y\otimes P|\Psi ⟩=\mathrm{Im}{\rho }_{\lambda }(g{)}_{ij}$（写出 $Y|0⟩,Y|1⟩$ 并展开交叉项）。进一步计算单次实验中主寄存器投影到 $|\lambda ,i,k⟩$ 的概率，并说明当 $|{\rho }_{\lambda }(g{)}_{ij}|$ 很小时，为什么估计它需要的样本数不受这个概率影响（提示：$X\otimes P$ 的期望本身是目标量）。
3. 维数守恒的数值练习。$S_4$ 的不可约表示由 $(4),(3,1),(2,2),(2,1,1),(1,1,1,1)$ 标记，维数依次为 $1,3,2,3,1$。验证 ${\sum }_{\lambda }{d}_{\lambda }^2=|S_4|$，并计算其中最大的表示矩阵有多少个矩阵元。
4. Kronecker 系数手算。模仿 5.3 节，用 $S_3$ 角色表计算 $V_{\mathrm{sign}}\otimes V_{\mathrm{std}}$ 的分解（提示：${\chi }_{\mathrm{sign}}\cdot {\chi }_{\mathrm{std}}$ 在各共轭类上的取值），给出 Kronecker 系数，并写出对应的三个测量概率（若有三个的话）。
5. Schur–Weyl 维数检查。取 $n=3,d=2$，出现的分拆为 $(3)$ 与 $(2,1)$：$\dim Q_{(3)}^2=4$（全对称张量）、$\dim P_{(3)}=1$、$\dim Q_{(2,1)}^2=2$、$\dim P_{(2,1)}=2$。验证 Schur–Weyl 分解两边的维数相等，并说明为什么 $\lambda =(1,1,1)$ 不出现。
6. 复杂度权衡。设 $p_{\nu }=2^{-n}$。分别估算普通采样与振幅估计把 $p_{\nu }$ 估到常数相对误差所需的调用次数（把 $ϵ$ 取为 $p_{\nu }$ 的常数倍代入 $O(1/{ϵ}^2)$ 与 $O(1/ϵ)$），并解释为什么此时加性估计无法区分 $g(\lambda ,\mu ,\nu )=0$ 与 $g(\lambda ,\mu ,\nu )=1$。

参考文献

• Zoo 编号 106：Stephen P. Jordan, Fast Quantum Algorithms for Approximating Some Irreducible Representations of Groups.
• Zoo 编号 196：Robert Beals, Quantum Computation of Fourier Transforms over Symmetric Groups, STOC 1997.
• Zoo 编号 197：Dave Bacon、Isaac Chuang 与 Aram Harrow, The Quantum Schur Transform: I. Efficient Qudit Circuits.
• Zoo 编号 460：Sergey Bravyi 等, Quantum Complexity of the Kronecker Coefficients.
• Zoo 编号 516：Martin Larocca 与 Vojtech Havlíček, Quantum Algorithms for Representation-Theoretic Multiplicities.
• Zoo 编号 515：Greta Panova, Polynomial Time Classical versus Quantum Algorithms for Representation Theoretic Multiplicities.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch09-algebra-number-theory/representation-matrix-elements
• 内容遵循 CC BY-NC-SA 4.0 许可协议