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

在 [Shor 算法](../ch04-classic-algorithms/shors-algorithm-tutorial.md) 中我们已经看到，循环群上的量子傅里叶变换（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 为什么产生不可约块、矩阵元如何经干涉读出、重数如何变成投影算子的秩，以及哪些量真的能高效算、哪些不能。

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

:::{admonition} 本课知识点
:class: tip

1. **[酉表示与不可约表示](#irrep-basics)**——能写出酉表示与不变子空间的定义，由同态条件推出 $\rho(e)=I$ 与 $\rho(g^{-1})=\rho(g)^\dagger$，并解释完全可约性为何把理解一切表示归结为不可约表示集合 $\widehat G$。
2. **[矩阵元估计任务与经典瓶颈](#matrix-element-problem)**——能陈述"输出单个复数而非整张矩阵"的加性估计问题，并从存储、构造、重数三个层面解释经典算法的瓶颈所在。
3. **[群 QFT 与正交关系](#group-qft-orthogonality)**——能写出群 QFT 的定义并用正则表示的角色推导 $\sum_{\lambda}d_\lambda^2=|G|$，能写出 Schur 正交关系并说明交结算子与 Schur 引理在证明中的角色。
4. **[块对角化与矩阵元读出](#block-diagonalization-readout)**——能推导 $F_GL_gF_G^\dagger=\bigoplus_\lambda\rho_\lambda(g)\otimes I_{d_\lambda}$，构造 Hadamard 测试分别读出矩阵元的实部与虚部，并比较采样与振幅估计两种精度—代价模式。
5. **[对称群 QFT 与 Schur 变换](#symmetric-group-schur)**——能列出分拆与标准 Young 表对 $S_n$ 不可约表示的标记，解释 Beals 电路沿子群塔逐级分解的思想，并写出 Schur–Weyl 分解、完成维数闭合检查。
6. **[表示重数与投影测量](#multiplicity-projection-measurement)**——能把 Kronecker 系数实现为等型投影算子的秩，证明角色投影公式 $\Pi_\nu=\frac{d_\nu}{|G|}\sum_g\chi_\nu(g)^*\rho_W(g)$，并推导最大混合态上的接受概率 $p_\nu=\frac{g(\lambda,\mu,\nu)\,d_\nu}{d_\lambda d_\mu}$。
7. **[加性估计的边界与经典对照](#additive-estimation-boundary)**——能比较加性估计与精确整数计算，说明 $p_\nu$ 指数小时为何需要指数资源，并结合 Panova 2025 的经典算法进展核对量子优势结论。
8. **[S₃ 完整演算](#s3-worked-example)**——能计算 $S_3$ 的角色表、标准表示矩阵与 $V_{\rm std}\otimes V_{\rm std}$ 的分解，完成维数与概率的守恒检查，并说明 Hadamard 测试如何读出具体矩阵元。

:::

## 1. 计算任务是什么

(irrep-basics)=
### 1.1 表示与不可约表示

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

$$
\rho:G\to U(V),
\qquad \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)^\dagger$（酉矩阵的逆等于共轭转置）。

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

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

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

(matrix-element-problem)=
### 1.2 任务陈述：估计单个矩阵元

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

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

$$
\bigl|\tilde\rho-\rho_\lambda(g)_{ij}\bigr|\le\epsilon,
\qquad\text{其中}\qquad
\rho_\lambda(g)_{ij}=\langle i|\rho_\lambda(g)|j\rangle
$$

是 $\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、引入正交关系、逐步计算共轭作用、用干涉电路读出矩阵元。

(group-qft-orthogonality)=
### 2.1 群上的量子傅里叶变换

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

$$
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.
$$

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

$$
\sum_{\lambda\in\widehat G}d_\lambda^2=|G|,
$$

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

$$
\chi_{\rm reg}(g)=
\begin{cases}
|G|, & g=e,\\
0, & g\neq e.
\end{cases}
$$

另一方面，任何表示分解为不可约表示时，$\lambda$ 出现的重数等于角色内积 $\frac{1}{|G|}\sum_g\chi_{\rm reg}(g)^*\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\widehat G$，则对任意指标 $i,j,k,l$，

$$
\sum_{g\in G}
\rho_\lambda(g)_{ij}^{*}\,
\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\rangle\langle 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)^\dagger$ 展开成分量就是定理中的形式。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)^*\chi_\mu(g)
=\delta_{\lambda\mu}.
$$

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

(block-diagonalization-readout)=
### 2.3 块对角化：逐步推导

定义**左乘酉算子**

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

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

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

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

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

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

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

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

$$
L_gF_G^\dagger|\lambda,i,j\rangle
=\sqrt{\frac{d_\lambda}{|G|}}
\sum_{y\in G}\rho_\lambda(g^{-1}y)_{ij}^{*}\,|y\rangle.
$$

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

$$
F_GL_gF_G^\dagger|\lambda,i,j\rangle
=\sum_{\mu\in\widehat G}
\frac{\sqrt{d_\lambda d_\mu}}{|G|}
\sum_{a,b=1}^{d_\mu}
\Bigl[\sum_{y\in G}
\rho_\lambda(g^{-1}y)_{ij}^{*}\,
\rho_\mu(y)_{ab}\Bigr]
|\mu,a,b\rangle.
$$

现在处理方括号里的群求和，这是整个推导的关键一步。先用同态性质把 $\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}^{*}\,
\rho_\mu(y)_{ab}
=\sum_{c}\rho_\lambda(g^{-1})_{ic}^{*}
\Bigl[\sum_{y\in G}
\rho_\lambda(y)_{cj}^{*}\,
\rho_\mu(y)_{ab}\Bigr].
$$

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

$$
\sum_{y\in G}
\rho_\lambda(y)_{cj}^{*}\,
\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}
\Big|_{\mu=\lambda}=1,
$$

于是

$$
F_GL_gF_G^\dagger|\lambda,i,j\rangle
=\sum_{a}\rho_\lambda(g^{-1})_{ia}^{*}\,|\lambda,a,j\rangle
=\sum_{a}\rho_\lambda(g)_{ai}\,|\lambda,a,j\rangle,
$$

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

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

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

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

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

$$
|\Psi\rangle
=\frac{1}{\sqrt2}\Bigl(
|0\rangle\,|\lambda,j,k\rangle
+|1\rangle\,W|\lambda,j,k\rangle
\Bigr).
$$

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

$$
\langle\Psi|X\otimes P|\Psi\rangle
=\frac12\Bigl(
\langle\lambda,j,k|PW|\lambda,j,k\rangle
+\langle\lambda,j,k|W^\dagger P|\lambda,j,k\rangle
\Bigr).
$$

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

$$
\langle\Psi|X\otimes P|\Psi\rangle
=\frac12\bigl(\rho_\lambda(g)_{ij}+\rho_\lambda(g)_{ij}^{*}\bigr)
=\operatorname{Re}\rho_\lambda(g)_{ij}.
$$

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

$$
\langle\Psi|Y\otimes P|\Psi\rangle
=\operatorname{Im}\rho_\lambda(g)_{ij}.
$$

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

### 2.5 复杂度分析

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

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

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

## 3. 对称群与 Schur 变换

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

(symmetric-group-schur)=
### 3.1 对称群的不可约表示

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

$$
\lambda\vdash n,
\qquad
\lambda=(\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_{\ell}>0),
\quad \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\rangle$ 中的每个标签都有多项式比特长度的组合编码——这是"多项式电路"得以谈论的前提。

### 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/\epsilon$ 的多项式时间内以加性误差 $\epsilon$ 估计。这里的输入是 $(\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\rangle\otimes\cdots\otimes|v_n\rangle=|v_{\sigma^{-1}(1)}\rangle\otimes\cdots\otimes|v_{\sigma^{-1}(n)}\rangle$。

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

$$
(\mathbb C^d)^{\otimes n}
\cong\bigoplus_{\substack{\lambda\vdash n\\ \ell(\lambda)\le d}}
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)^{\otimes2}
=\underbrace{\mathrm{Sym}^2}_{\lambda=(2)}
\oplus
\underbrace{\wedge^2}_{\lambda=(1,1)},
\qquad
\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_{\rm Sch}$ 就是显式完成这个换基的酉矩阵：把"张量积基"换成"$|\lambda,q,p\rangle$ 基"（$q$ 为 $Q_\lambda^d$ 的指标，$p$ 为 $P_\lambda$ 的指标）。Bacon、Chuang 与 Harrow（Zoo 编号 197）给出了关于 $n$、$\log d$ 和 $1/\epsilon$ 多项式规模的 Schur 变换量子电路，方法同样是沿 $n$ 逐个加入张量因子、用 Clebsch–Gordan 型的受控旋转逐级耦合。

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

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

$$
U_{\rm Sch}\,U^{\otimes n}\,U_{\rm Sch}^\dagger
=\bigoplus_{\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. 从矩阵元到表示重数

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

(multiplicity-projection-measurement)=
### 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\operatorname{Hom}_{S_n}
(V_\nu,\,V_\lambda\otimes V_\mu),
$$

其中 $\operatorname{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)^*\,\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)^*\,\rho_W(hgh^{-1}),
$$

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

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

$$
\operatorname{Tr}_{V_\sigma}(\Pi_\nu)
=\frac{d_\nu}{|G|}\sum_{g}\chi_\nu(g)^*\,\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$ 维，故

$$
\operatorname{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
=\operatorname{Tr}\Bigl(\Pi_\nu\,\frac{I}{d_\lambda d_\mu}\Bigr)
=\frac{\operatorname{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$ 做加性 $\epsilon$ 估计，普通采样需 $O(1/\epsilon^2)$ 次实验，振幅估计在相干模型下需 $O(1/\epsilon)$ 次调用。每次实验的电路（$S_n$ QFT、投影测量的实现）关于 $n$ 为多项式。

(additive-estimation-boundary)=
### 4.4 保留条款：加性估计不等于精确计算

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

- **可加性估计**：当 $p_\nu$ 不太小（例如关于 $n$ 是多项式小的倒数），取 $\epsilon$ 为同量级即可以多项式代价把 $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$），就需要 $\epsilon<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 个）。

(s3-worked-example)=
### 5.1 三个不可约表示与角色表

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

- **平凡表示** $V_{\rm triv}$（$\lambda=(3)$）：$d=1$，$\chi_{\rm triv}(g)=1$；
- **符号表示** $V_{\rm sign}$（$\lambda=(1,1,1)$）：$d=1$，$\chi_{\rm sign}(g)=\operatorname{sgn}(g)$，对换取 $-1$、三循环取 $1$；
- **标准表示** $V_{\rm 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_{\rm triv}\oplus V_{\rm std}$（对角线方向是平凡子表示），角色相减：

$$
\chi_{\rm std}=\chi_{\rm perm}-\chi_{\rm triv}:
\qquad
\begin{array}{c|ccc}
 & e & (\cdot\cdot) & (\cdot\cdot\cdot)\\\hline
\chi_{\rm perm} & 3 & 1 & 0\\
\chi_{\rm 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 的酉变换只能是 $\pm120^\circ$ 旋转。取适当正交归一基，

$$
\rho_{\rm std}((123))=
\begin{pmatrix}
-\tfrac12&-\tfrac{\sqrt3}{2}\\[2pt]
\tfrac{\sqrt3}{2}&-\tfrac12
\end{pmatrix}.
$$

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

- **角色**：$\chi_{\rm std}((123))=-\tfrac12-\tfrac12=-1$，与角色表一致；也等于 $2\cos120^\circ=-1$（二维旋转的迹公式）。
- **阶**：$\cos(3\cdot120^\circ)=\cos360^\circ=1$，故 $\rho_{\rm std}((123))^3=I=\rho_{\rm std}(e)$，同态要求满足。
- **矩阵元**：例如 $\rho_{\rm std}((123))_{11}=-\tfrac12$，$\rho_{\rm std}((123))_{21}=\tfrac{\sqrt3}{2}$。

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

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

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

$$
\chi_{\rm std}^2:\quad
e\mapsto 4,\quad
(\cdot\cdot)\mapsto 0,\quad
(\cdot\cdot\cdot)\mapsto 1.
$$

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

$$
\begin{aligned}
\langle\chi_{\rm std}^2,\chi_{\rm triv}\rangle
&=\tfrac16\bigl(1\cdot4\cdot1+3\cdot0\cdot1+2\cdot1\cdot1\bigr)
=\tfrac{6}{6}=1,\\
\langle\chi_{\rm std}^2,\chi_{\rm sign}\rangle
&=\tfrac16\bigl(1\cdot4\cdot1+3\cdot0\cdot(-1)+2\cdot1\cdot1\bigr)
=1,\\
\langle\chi_{\rm std}^2,\chi_{\rm std}\rangle
&=\tfrac16\bigl(1\cdot4\cdot2+3\cdot0\cdot0+2\cdot1\cdot(-1)\bigr)
=\tfrac{8-2}{6}=1.
\end{aligned}
$$

三个重数均为 1，即

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

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

### 5.4 投影测量的数值

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

$$
p_{\rm triv}=\frac{1\cdot1}{4}=\frac14,
\qquad
p_{\rm sign}=\frac{1\cdot1}{4}=\frac14,
\qquad
p_{\rm std}=\frac{1\cdot2}{4}=\frac12.
$$

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

## 6. 小结

- 群 QFT 把左正则表示变为不可约表示的直和：$F_GL_gF_G^\dagger=\bigoplus_\lambda\rho_\lambda(g)\otimes I_{d_\lambda}$，推导的引擎是 Schur 正交关系。
- Hadamard/振幅估计读取单个矩阵元，输出只是一个复数，不需要写出指数大的矩阵；加性 $\epsilon$ 的代价为采样的 $O(1/\epsilon^2)$ 或相干模型的 $O(1/\epsilon)$。
- 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【酉表示与不可约表示】**（→ [1.1 节](#irrep-basics)）

1. 写出酉表示的定义（含同态条件 $\rho(gh)=\rho(g)\rho(h)$），并由它证明 $\rho(e)=I$ 与 $\rho(g^{-1})=\rho(g)^{-1}=\rho(g)^\dagger$。
2. 设 $S_3$ 按置换三个坐标轴作用在 $\mathbb C^3$ 上：验证子空间 $\operatorname{span}\{(1,1,1)\}$ 与平面 $x_1+x_2+x_3=0$ 都是不变子空间，由此说明置换表示可约，并指出对角子空间上实现的是哪一个一维不可约表示。

> 提示：验证不变子空间只需检查每个 $\rho(g)w$ 仍落在子空间内；注意任何置换都把 $(1,1,1)$ 映到自身。

**练习 2【矩阵元估计任务与经典瓶颈】**（→ [1.2 节](#matrix-element-problem)）

1. 复述矩阵元问题：给定 $G,\lambda,g,i,j,\epsilon$，算法要输出什么、满足什么精度条件；并解释为什么"答案只是一个复数"使得关于 $\log d_\lambda$ 的多项式运行时间并不自相矛盾。
2. 用 Stirling 近似 $\ln(n!)\approx n\ln n-n+\tfrac12\ln(2\pi n)$ 验证 $\log_2(100!)\approx 525$，并据此说明：当 $d_\lambda$ 达到 $\sqrt{n!}$ 量级时，显式写出 $\rho_\lambda(g)$ 需要约多少个复数元，与一条 $\operatorname{poly}(n)$ 规模的电路相比差距有多大。

> 提示：矩阵元个数是 $d_\lambda^2$；换底公式 $\log_2 x=\ln x/\ln 2$。

**练习 3【群 QFT 与正交关系】**（→ [2.1 节](#group-qft-orthogonality)）

1. **维数守恒的数值练习**。$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|$，并计算其中最大的表示矩阵有多少个矩阵元。
2. 写出 $F_G|x\rangle$ 的定义式，并分别说明输出标签 $(\lambda,i,j)$ 中三个指标的含义：哪个是表示标签、哪个是行指标、哪个是重数指标。
3. 在 Schur 正交关系中取 $i=j$、$k=l$ 并对 $i,k$ 求和，推导角色正交关系 $\frac{1}{|G|}\sum_{g\in G}\chi_\lambda(g)^*\chi_\mu(g)=\delta_{\lambda\mu}$。

> 提示：$\sum_i\rho_\lambda(g)_{ii}=\chi_\lambda(g)$；对 $i,k$ 求和时 $\sum_{i,k}\delta_{ik}=d_\lambda$。

**练习 4【块对角化与矩阵元读出】**（→ [2.3 节](#block-diagonalization-readout)）

1. 写出块对角化公式 $F_GL_gF_G^\dagger=\bigoplus_{\lambda\in\widehat G}\rho_\lambda(g)\otimes I_{d_\lambda}$，并说明 2.3 节推导中三个 Kronecker $\delta$ 分别把哪些求和指标钉死在何处——块对角结构与 $I_{d_\lambda}$ 因子各来自哪一个？
2. **块对角化的另一半**。2.3 节处理了左乘 $L_g|x\rangle=|gx\rangle$。定义右乘 $R_g|x\rangle=|xg^{-1}\rangle$，模仿三步推导计算 $F_GR_gF_G^\dagger$ 在 $|\lambda,i,j\rangle$ 上的作用，说明它作用在哪个指标上、以何种转置/共轭形式出现，并由此解释块结构中 $I_{d_\lambda}$ 因子的来源。
3. **Hadamard 测试的虚部**。补全 2.4 节的计算：验证 $\langle\Psi|Y\otimes P|\Psi\rangle=\operatorname{Im}\rho_\lambda(g)_{ij}$（写出 $Y|0\rangle,Y|1\rangle$ 并展开交叉项）。进一步计算单次实验中主寄存器投影到 $|\lambda,i,k\rangle$ 的概率，并说明当 $|\rho_\lambda(g)_{ij}|$ 很小时，为什么估计它需要的样本数不受这个概率影响（提示：$X\otimes P$ 的期望本身是目标量）。

> 提示（第 2 题）：换求和变量 $y=xg^{-1}$ 后，用同态性质把 $\rho_\lambda(yg)$ 拆成两个矩阵元的乘积，再交给 Schur 正交关系处理。

**练习 5【对称群 QFT 与 Schur 变换】**（→ [3.1 节](#symmetric-group-schur)）

1. 用 hook-length 公式计算形状 $(2,1)$ 的标准 Young 表个数，验证 $d_{(2,1)}=2$，并写出这两个标准表。
2. 解释 Beals 的 $S_n$ QFT 为何能沿子群塔 $S_1\subset S_2\subset\cdots\subset S_n$ 逐层分解、每层按分支规则做受控旋转，并说明"每个标签都有多项式比特的组合编码"为何是谈论多项式电路的前提。
3. **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)$ 不出现。

> 提示：条件 $\ell(\lambda)\le d$ 排除三行分拆；左边总维数是 $2^3$。

**练习 6【表示重数与投影测量】**（→ [4.1 节](#multiplicity-projection-measurement)）

1. 解释 Kronecker 系数 $g(\lambda,\mu,\nu)=\dim\operatorname{Hom}_{S_n}(V_\nu,\,V_\lambda\otimes V_\mu)$ 为何数出 $V_\nu$ 的出现次数，并由 $\operatorname{rank}\Pi_\nu=g(\lambda,\mu,\nu)\,d_\nu$ 推导最大混合态上的接受概率 $p_\nu=\frac{g(\lambda,\mu,\nu)\,d_\nu}{d_\lambda d_\mu}$，逐因子说明分子与分母的来源。
2. 仿照 4.2 节的论证，证明 $\Pi_\nu\Pi_\mu=\delta_{\nu\mu}\Pi_\nu$ 且 $\sum_{\nu\in\widehat G}\Pi_\nu=I_W$，并解释为什么这保证 $\sum_\nu p_\nu=1$。

> 提示：把 $W$ 分解为不可约直和后逐块检查——$\Pi_\nu$ 在每个 $V_\nu$ 成分上是恒等、在其余成分上是零。

**练习 7【加性估计的边界与经典对照】**（→ [4.4 节](#additive-estimation-boundary)）

1. 设 $p_\nu=\frac{1}{n^2}$：分别用采样代价 $O(1/\epsilon^2)$ 与振幅估计代价 $O(1/\epsilon)$ 估算把 $p_\nu$ 估到 $\epsilon=\frac{p_\nu}{2}$ 所需的实验次数，验证两者都只是 $n$ 的多项式。
2. 根据 4.5 节比较量子算法与 Panova 2025 经典算法在 Kronecker 系数上的现状：在哪些参数族上现有结论只支持多项式级差距？为什么不能笼统宣称指数加速？
3. **复杂度权衡**。设 $p_\nu=2^{-n}$。分别估算普通采样与振幅估计把 $p_\nu$ 估到**常数相对误差**所需的调用次数（把 $\epsilon$ 取为 $p_\nu$ 的常数倍代入 $O(1/\epsilon^2)$ 与 $O(1/\epsilon)$），并解释为什么此时加性估计无法区分 $g(\lambda,\mu,\nu)=0$ 与 $g(\lambda,\mu,\nu)=1$。

> 提示：$\epsilon=\Theta(2^{-n})$ 对应 $2^{2n}$ 与 $2^n$ 次调用；要区分 $g=0$ 与 $g=1$，加性误差必须小于两种情形的 $p_\nu$ 之差。

**练习 8【S₃ 完整演算】**（→ [5.1 节](#s3-worked-example)）

1. 验证 5.2 节给出的 $\rho_{\rm std}((123))$：计算它的迹并与角色表比较，再计算其三次幂验证 $\rho_{\rm std}((123))^3=I$。
2. 由 $\chi_{\rm perm}=(3,1,0)$ 减去 $\chi_{\rm triv}=(1,1,1)$ 得 $\chi_{\rm std}$，用 $1^2+1^2+2^2=6$ 验证维数守恒；再由 $\operatorname{rank}\Pi_\nu=g\,d_\nu$ 算出 $V_{\rm std}\otimes V_{\rm std}$ 上三个投影的秩，验证秩之和等于 $4$。
3. **Kronecker 系数手算**。模仿 5.3 节，用 $S_3$ 角色表计算 $V_{\rm sign}\otimes V_{\rm std}$ 的分解，给出 Kronecker 系数，并写出对应的三个测量概率（若有三个的话）。

> 提示：先算 $\chi_{\rm sign}\cdot\chi_{\rm std}$ 在三个共轭类上的取值，再做加权内积；用维数检查 $1\times 2=2$ 收尾。

## 参考文献

- 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).