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

在 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 为什么产生不可约块、矩阵元如何经干涉读出、重数如何变成投影算子的秩，以及哪些量真的能高效算、哪些不能。

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

本课知识点

  1. 酉表示与不可约表示——能写出酉表示与不变子空间的定义，由同态条件推出 \(\rho(e)=I\) 与 \(\rho(g^{-1})=\rho(g)^\dagger\)，并解释完全可约性为何把理解一切表示归结为不可约表示集合 \(\widehat G\)。

  2. 矩阵元估计任务与经典瓶颈——能陈述"输出单个复数而非整张矩阵"的加性估计问题，并从存储、构造、重数三个层面解释经典算法的瓶颈所在。

  3. 群 QFT 与正交关系——能写出群 QFT 的定义并用正则表示的角色推导 \(\sum_{\lambda}d_\lambda^2=|G|\)，能写出 Schur 正交关系并说明交结算子与 Schur 引理在证明中的角色。

  4. 块对角化与矩阵元读出——能推导 \(F_GL_gF_G^\dagger=\bigoplus_\lambda\rho_\lambda(g)\otimes I_{d_\lambda}\)，构造 Hadamard 测试分别读出矩阵元的实部与虚部，并比较采样与振幅估计两种精度—代价模式。

  5. 对称群 QFT 与 Schur 变换——能列出分拆与标准 Young 表对 \(S_n\) 不可约表示的标记，解释 Beals 电路沿子群塔逐级分解的思想，并写出 Schur–Weyl 分解、完成维数闭合检查。

  6. 表示重数与投影测量——能把 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. 加性估计的边界与经典对照——能比较加性估计与精确整数计算，说明 \(p_\nu\) 指数小时为何需要指数资源，并结合 Panova 2025 的经典算法进展核对量子优势结论。

  8. S₃ 完整演算——能计算 \(S_3\) 的角色表、标准表示矩阵与 \(V_{\rm std}\otimes V_{\rm std}\) 的分解，完成维数与概率的守恒检查，并说明 Hadamard 测试如何读出具体矩阵元。

1. 计算任务是什么

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)\)。

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

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\)，故

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

另一方面，任何表示分解为不可约表示时，\(\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 节构造投影算子时，我们还会再用一次。

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 变换。

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 对偶断言，不仅如此，它们还互为对方在这个空间里的全部对称：整个空间分解为

\[\begin{split} (\mathbb C^d)^{\otimes n} \cong\bigoplus_{\substack{\lambda\vdash n\\ \ell(\lambda)\le d}} Q_\lambda^d\otimes P_\lambda, \end{split}\]

其中 \(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. 从矩阵元到表示重数

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

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\) 为多项式。

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 个）。

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}\)（对角线方向是平凡子表示），角色相减：

\[\begin{split} \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} \end{split}\]

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\) 旋转。取适当正交归一基，

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

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

  • 角色：\(\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{split} \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} \end{split}\]

三个重数均为 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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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\) 收尾。

参考文献