# 群表示的矩阵元与重数：QFT、Schur 变换和投影测量

群表示把抽象群元素变成酉矩阵。经典算法若显式写出一个指数维不可约表示，连存储矩阵都做不到；量子计算却可把该矩阵作为一个酉子块直接作用在量子态上，再用干涉估计单个矩阵元。本课先推导“群 QFT 将正则表示块对角化”，再说明 Kronecker 等重数如何变成投影算子的秩，并结合 2025 年的经典改进厘清量子优势边界。

## 1. 计算任务是什么

群 $G$ 的酉表示是同态

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

若 $V$ 没有非平凡不变子空间，表示不可约。给定不可约表示标签 $\lambda$、群元素 $g$ 和基向量标签 $i,j$，矩阵元问题要求以加性误差 $\epsilon$ 估计

$$
\rho_\lambda(g)_{ij}
=\langle i|\rho_\lambda(g)|j\rangle.
$$

输出只是一个复数，而不是整张 $d_\lambda\times d_\lambda$ 矩阵。这一区分允许算法关于 $\log d_\lambda$ 多项式运行，即使 $d_\lambda$ 本身指数大。

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

有限群上的量子傅里叶变换按如下约定作用：

$$
F_G|x\rangle
=\sum_{\lambda\in\widehat G}
\sqrt{\frac{d_\lambda}{|G|}}
\sum_{i,j=1}^{d_\lambda}
\rho_\lambda(x)_{ij}
|\lambda,i,j\rangle.
$$

这里 $\widehat G$ 是不可约表示集合，且 $\sum_\lambda d_\lambda^2=|G|$ 保证维数守恒。定义左乘酉算子

$$
L_g|x\rangle=|gx\rangle.
$$

把变量 $x$ 换为 $g^{-1}x$ 并使用表示同态，可得

$$
F_G L_g F_G^\dagger
=\bigoplus_{\lambda\in\widehat G}
\rho_\lambda(g)\otimes I_{d_\lambda},
$$

具体由共轭或转置出现在哪个指标取决于 QFT 约定。物理意义不变：容易实现的“群元素左乘”经 QFT 换基后，自动在每个表示标签区执行目标不可约矩阵。

若 $F_G$、$F_G^\dagger$ 和 $L_g$ 都有多项式大小电路，就不必显式生成 $\rho_\lambda(g)$。准备 $|\lambda,j,k\rangle$，执行上述块酉，再让结果与 $|\lambda,i,k\rangle$ 干涉；测量控制比特的 $X$、$Y$ 期望分别给出矩阵元的实部和虚部。加性误差 $\epsilon$ 的普通采样需要 $O(1/\epsilon^2)$ 次，振幅估计可在相干访问模型下降到 $O(1/\epsilon)$。

## 3. 对称群与 Schur 变换

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

$$
\lambda\vdash n
$$

标记，表示基可用标准 Young 表编码。Beals 给出了高效的 $S_n$ 量子 Fourier 变换，因此可以高效实现任意 $S_n$ 不可约表示的单个矩阵元估计。

连续群 $U(d)$ 的对应工具是 Schur 变换。Schur--Weyl 对偶给出

$$
(\mathbb C^d)^{\otimes n}
\cong\bigoplus_{\lambda\vdash n,\,\ell(\lambda)\le d}
Q_\lambda^d\otimes P_\lambda,
$$

其中 $Q_\lambda^d$ 承载 $U(d)$ 不可约表示，$P_\lambda$ 承载 $S_n$ 不可约表示。Schur 变换显式完成这个换基；共轭物理上自然的 $U^{\otimes n}$ 后，就得到各 $Q_\lambda^d(U)$ 的块。对多项式最高权的 $U(n),SU(n),SO(n)$ 表示，也可通过类似分支规则构造多项式电路。

## 4. 从矩阵元到表示重数

重数回答“某个不可约表示在分解中出现多少次”。例如 Kronecker 系数

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

是张量积 $V_\lambda\otimes V_\mu$ 中 $V_\nu$ 的出现次数。

角色正交关系给出投影到 $\nu$-等型分量的算子

$$
\Pi_\nu
=\frac{d_\nu}{|S_n|}
\sum_{g\in S_n}
\chi_\nu(g)^*
\bigl(\rho_\lambda(g)\otimes\rho_\mu(g)\bigr).
$$

其秩为

$$
\operatorname{rank}(\Pi_\nu)
=g(\lambda,\mu,\nu)d_\nu.
$$

量子 QFT 可以在叠加中选择表示标签并测量该投影。若在 $V_\lambda\otimes V_\mu$ 的最大混合态上测量，接受概率为

$$
p_\nu=
\frac{g(\lambda,\mu,\nu)d_\nu}
{d_\lambda d_\mu}.
$$

因此采样或振幅估计可加性逼近**归一化** Kronecker 系数。若 $p_\nu$ 指数小，要恢复未归一化整数或获得相对误差仍可能需要指数次采样；“可测投影”不等于“所有重数都能高效精确计算”。

Larocca--Havlíček 将这种思路推广到 Kostka、Littlewood--Richardson、plethysm 与 Kronecker 重数，并明确要求相关表示维数比为多项式。Panova 随后给出许多同一参数区间的经典多项式算法，推翻了部分超多项式加速猜想；现有结论在若干族上只支持多项式量子--经典差距，plethysm 等其余范围仍需逐项分析。

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

$S_3$ 有平凡、符号和二维标准表示。三循环 $(123)$ 在标准表示中是平面旋转 $120^\circ$：

$$
\rho_{\rm std}((123))=
\begin{pmatrix}
-\tfrac12&-\tfrac{\sqrt3}{2}\\
\tfrac{\sqrt3}{2}&-\tfrac12
\end{pmatrix},
\qquad \chi_{\rm std}((123))=-1.
$$

QFT 块电路可用 Hadamard 干涉分别估计四个矩阵元。张量积分解为

$$
V_{\rm std}\otimes V_{\rm std}
\cong V_{\rm triv}\oplus V_{\rm sign}\oplus V_{\rm std},
$$

三个重数均为 1；维数检查 $2\times2=1+1+2$ 正好闭合。

## 6. 小结与习题

- 群 QFT 把左正则表示变为不可约表示的直和。
- Hadamard/振幅估计读取单个矩阵元，不需要输出指数大的矩阵。
- Schur 变换同时组织 $U(d)$ 与 $S_n$ 表示。
- 表示重数是投影秩；高效可得的通常是带维数归一化的加性估计。
- 量子优势必须随 2025 年经典算法更新，不能沿用已被推翻的猜想。

1. 从 QFT 定义推导 $F_GL_gF_G^\dagger$ 的块对角形式。
2. 设计一个控制比特电路，分别得到 $\langle i|U|j\rangle$ 的实部与虚部。
3. 用角色表验证 $S_3$ 标准表示张量平方的分解。
4. 若 $p_\nu=2^{-n}$，估算普通采样和振幅估计得到常数相对误差所需调用数。

## 参考文献

- Zoo 编号 106：Stephen P. Jordan, [Fast Quantum Algorithms for Approximating Some Irreducible Representations of Groups](https://arxiv.org/abs/0811.0562).
- 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](https://arxiv.org/abs/quant-ph/0601001).
- Zoo 编号 460：Sergey Bravyi 等, [Quantum Complexity of the Kronecker Coefficients](https://arxiv.org/abs/2302.11454).
- Zoo 编号 516：Martin Larocca 与 Vojtech Havlíček, [Quantum Algorithms for Representation-Theoretic Multiplicities](https://arxiv.org/abs/2407.17649).
- Zoo 编号 515：Greta Panova, [Polynomial Time Classical versus Quantum Algorithms for Representation Theoretic Multiplicities](https://arxiv.org/abs/2502.20253).