群表示的矩阵元与重数：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\)：

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

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}\)，估算普通采样和振幅估计得到常数相对误差所需调用数。

参考文献