三维流形不变量：Heegaard Splitting、Turaev--Viro 状态和与量子通用性¶
在前面关于结不变量的教程中，我们研究的是三维空间中的一维对象——嵌入 \(S^3\) 的圆周。本教程把维度再抬高一格：三维流形本身也有由量子群与拓扑量子场论（TQFT）构造的标量不变量。其中最著名的是 Turaev--Viro invariant：它可以写成 triangulation 上 quantum \(6j\) 符号的状态和，也可以通过 Heegaard splitting 改写成 mapping class group 表示的真空振幅的模平方。前一种写法是定义，后一种写法是算法——正是后者给出了一条多项式时间的量子算法，并且在特定的误差尺度下，逼近这个不变量本身就是 BQP-universal 的：任何量子计算都可以编码进一个三维流形的 Turaev--Viro invariant 里。
为什么值得关心这件事？三维流形的 homeomorphism 问题（判定两个三维流形是否同胚）是低维拓扑的核心问题之一。它在经典计算中是可判定的，但已知的判定过程极其缓慢，而且依赖 Thurston 几何化纲领这样的深刻结构定理；对实际规模几乎没有可操作的算法。拓扑不变量是区分流形的第一道筛子：若 \(TV_r(M)\neq TV_r(M')\)，则 \(M\) 与 \(M'\) 一定不同胚。因此"能不能高效计算不变量"是一个自然的算法问题。本教程的主线是：
先用组合语言（triangulation + 着色）定义 Turaev--Viro invariant，看清它为什么经典上难算；
再用 TQFT 语言（Heegaard splitting + mapping class group 表示）改写同一个量，看清它为什么量子上好算；
最后说明这种"好算"强到什么程度——它足以模拟任意量子电路（BQP-hardness），以及这个结论的适用边界在哪里。
历史脉络（与文末参考文献对应）。 Turaev 与 Viro 于 1992 年用 quantum \(6j\) 符号的状态和定义了该不变量；与之密切相关的 Reshetikhin--Turaev 不变量（1991）来自模张量范畴的手术构造。量子算法一侧：Garnerone、Marzuoli 与 Rasetti（Zoo 编号 114）给出处理若干三维流形拓扑不变量的量子 spin-network 方案；Kauffman 与 Lomonaco（Zoo 编号 115）系统建立了 q-deformed spin network、结多项式与 anyonic 拓扑量子计算之间的联系；Alagic、Jordan、König 与 Reichardt（Zoo 编号 129）则证明了在 Heegaard splitting 输入与论文指定的加性归一化下，逼近 Turaev--Viro invariant 对量子计算机是完备的（BQP-complete）。最后一项结果是本教程的高潮，我们将花一整节解释它的含义与保留条款。
前置知识。 我们假定读者熟悉量子线路、Hadamard test、振幅估计的采样复杂度（第 3、5 章），并了解张量范畴只需要"对象、融合规则、结合子"这个层次的直觉；所有范畴论概念都会就地定义。
本课知识点
三角剖分与 Heegaard 分解——能写出两种输入表示的规模度量（\(T\) 与 \((g,m)\)），并解释复杂度结论为何必须注明所用的表示。
量子维数与 quantum 6j 符号——能计算量子整数、量子维数 \(d_j\) 与总量子维数 \(\mathcal D^2\)，并列出融合可容许性条件与 quantum \(6j\) 符号的正交、五边形两条恒等式。
Turaev--Viro 状态和与 Pachner 不变性——能写出状态和公式，把 \(2\leftrightarrow3\)、\(1\leftrightarrow4\) 两类 move 下的不变性分别对应到五边形恒等式与加权正交关系，并估算着色项数说明经典枚举为何指数慢。
TQFT 字典与真空振幅——能解释"粘合=算子复合/内积"字典，写出 \(TV_r(M)\propto\bigl|\langle\Omega_g|\rho_r(\varphi)|\Omega_g\rangle\bigr|^2\)，并用 Verlinde 公式说明态空间维数随 genus 指数增长。
融合基与局部门编译——能描述融合基的编码方式与 \(F\) move、\(R\) move、Dehn twist 三类局部门，并推导长度 \(m\) 的 gluing word 的电路规模为 \(\operatorname{poly}(g,m)\)。
Hadamard test 与误差传播——能推导 \(p_0=\tfrac12(1+\operatorname{Re}\,a)\) 与采样数 \(K=\Theta(1/\varepsilon^2)\)，并估计模平方一步的误差传播、比较加性与相对近似。
BQP 通用性与保留条款——能概述"表示稠密＋电路编译"两个证明要件，并逐条复述 level、输入表示、归一化精度三条保留条款划定的边界。
Genus-1 手算实例——能在 \(r=3\) 的环面例子中计算 modular \(S\)、\(T\) 矩阵与真空矩阵元的模平方，并对照 \(TV_3(S^3)=1/2\) 验证归一化。
1. 两种输入表示¶
一个闭定向三维流形 \(M\) 是一个没有边界的紧致三维空间，局部地看每一点都有 \(\mathbb R^3\) 的邻域。要把它交给算法，必须先选一种有限组合描述。常用的有两种，它们的"输入大小"差别很大，本节的要点是：谈论复杂度之前必须先说清楚用的是哪一种表示。
表示一：triangulation（三角剖分）。 把 \(M\) 切成有限个四面体（tetrahedra），并记录哪些三角形面按什么方式两两粘合。三维流形定理保证每个闭三维流形都存在三角剖分，且任意两个三角剖分之间可通过有限步 Pachner move 互变（这是第 4 节不变性证明的基础）。输入大小用四面体数 \(T\) 衡量。
表示二：Heegaard splitting（Heegaard 分解）。 取 genus \(g\) 的 handlebody \(H_g\)——直观上是一块有 \(g\) 个"把手"的实心体，例如 \(g=1\) 是实心环面（甜甜圈）。取两块完全相同的 \(H_g\)，沿着它们的边界曲面 \(\Sigma_g=\partial H_g\) 用一个曲面自同胚 \(\varphi\) 把对应点粘起来：
每个闭三维流形都存在 Heegaard splitting（例如沿三角剖分的 1-骨架加厚即得一个 handlebody）。粘合映射 \(\varphi\) 活在曲面 \(\Sigma_g\) 的 mapping class group（映射类群，记作 \(\mathrm{MCG}(\Sigma_g)\)）里：它是曲面自同胚在连续形变（isotopy）下的等价类。\(\mathrm{MCG}(\Sigma_g)\) 是有限生成的群，生成元可以取若干条简单闭曲线上的 Dehn twist（沿曲线剪开、扭转 \(2\pi\)、再粘回）。因此 \(\varphi\) 可以用生成元写成长度为 \(m\) 的 word 来描述，输入大小由二元组 \((g,m)\) 衡量。
量子算法对后一种表示最自然，原因是结构性的：TQFT 直接给每个 mapping class \(\varphi\) 分配一个酉算子，而酉算子正是量子线路能说母语的对象。
需要注意的是，两种表示的"大小"可以相差巨大：一个 \(T\) 很大的三角剖分可能描述一个 genus 很小、word 很短的流形，反之，把一个长 word 转成显式三角剖分也可能付出多项式但可观的代价。因此本教程中凡是出现"关于输入多项式"的说法，我们都会注明是关于 \(T\) 还是关于 \((g,m)\)——BQP-hardness 结果特指后者。
2. 组合数据：anyon 标签、量子维数与量子 \(6j\) 符号¶
Turaev--Viro 状态和里的每一项由三类数构成：边的标签、每条边的量子维数、每个四面体的 quantum \(6j\) 符号。本节把它们逐个定义清楚。直觉上，这些数据来自一个有限融合范畴（fusion category）——可以理解为"有限多种 anyon 的代数"——但组合层面只需要下面的具体规则。
Level 与标签集。 固定整数 \(r\ge 3\)（称为 level；对应单位根 \(q=e^{2\pi i/r}\)）。允许的标签是有限的自旋集合，对 \(SU(2)\) 理论取
共 \(r-1\) 个值。把 \(r\) 当作常数时，标签集的大小是常数；这一点在第 6 节的复杂度分析里会反复用到。
融合可容许性（fusion admissibility）。 不是任意三个标签都能出现在同一个三角面上。称三元组 \((j_1,j_2,j_3)\) 可容许，如果
前两个条件是普通角动量耦合的三角形规则（相当于经典 \(6j\) 符号的可容许性），最后一个不等式是"量子"截断：level \(r\) 禁止过大的总自旋。给三角剖分的每条边 \(e\) 赋一个标签 \(j_e\)，若每个三角面的三条边都满足可容许性，就称整个赋值是 admissible coloring。
量子整数与量子维数。 定义量子整数
第二个等号是把 \(q=e^{2\pi i/r}\) 代入、用 \(e^{ix}-e^{-ix}=2i\sin x\) 化简得到的；当 \(q\to1\) 时 \([n]_q\to n\)，所以它是普通整数的"q 形变"。每个标签 \(j\) 的**量子维数（quantum dimension）**定义为
注意 \(d_0=1\)，\(d_j>0\)，并且 \(d_j\) 一般不是整数——它度量的是 anyon \(j\) 的"有效自由度"，类似于普通表示论中不可约表示维数的角色。总量子维数为
其中第二个等号是正弦平方和的恒等式 \(\sum_{n=1}^{r-1}\sin^2(n\pi/r)=r/2\) 的直接应用。\(\mathcal D^2\) 是后文一切归一化的主角。
量子 \(6j\) 符号。 一个四面体有 6 条边，若其四个面都可容许，就赋给它一个复数
称为 quantum \(6j\) symbol。它可以用量子阶乘 \([n]_q!=[n]_q[n-1]_q\cdots[1]_q\) 的有限和显式写出（Racah 型公式），我们不需要这个显式形，只需要它的两条结构性性质，下一节会看到它们分别对应两种 Pachner move：
正交关系（orthogonality）：固定其余标签对某个内部标签求和时，配对的两个 \(6j\) 符号之积退化成 Kronecker \(\delta\)（乘以 \(d_j\) 的幂）。它表达"融合通道空间的基变换是酉的"。
五边形恒等式（pentagon identity）：三种不同重括号方式之间的变换相容——两种路径给出的复合变换相等。它表达"结合子（associator）的自洽性"，是 Mac Lane 相干定理在融合范畴中的体现。
这两个恒等式是范畴论公理的具体化，而对算法的全部意义在于：它们恰好是 Pachner move 的代数翻译，下一节逐步展示这一点。
3. Turaev--Viro 状态和：定义、不变性与经典瓶颈¶
3.1 定义¶
有了上面的数据，定义就是一句话：对所有 admissible coloring，把局部因子乘起来，再求和。
逐项解释：
求和跑遍三角剖分全部边的所有 admissible 标签赋值 \(\{j_e\}\)；
第一个乘积给每条边 \(e\) 一个量子维数因子 \(d_{j_e}\)（有些约定写成 \(d_{j_e}\) 或带符号 \((-1)^{2j_e}d_{j_e}\)，差别只影响整体约定）；
第二个乘积给每个四面体 \(\tau\) 一个 quantum \(6j\) 符号，其六个指标就是 \(\tau\) 六条边的标签；
\(\mathcal N(M,r)\) 是归一化因子，由顶点数的 \(\mathcal D^2\) 幂与总量子维数构成，其作用是让整个表达式在 Pachner move 下严格不变（下一小节会看到它如何抵消求和项数的变化）。
3.2 为什么这是拓扑不变量：Pachner move 逐步核对¶
三维流形的一个定理（Pachner）说：同一个流形的任意两个三角剖分，可由有限步 \(2\leftrightarrow3\) move 和 \(1\leftrightarrow4\) move 互变。 因此要证明 \(TV_r(M)\) 只依赖 \(M\) 的拓扑而不依赖具体三角剖分，只需验证状态和在两类 move 下不变。
\(2\)--\(3\) move（两个四面体变三个）。 两个共享一个三角面的四面体（共 5 个顶点、9 条边）可以重剖成三个共享一条内部边的四面体。move 两侧的状态和差别只在于：左侧对共享面内部不出现额外交错、右侧对新的内部边标签求和。把两侧局部因子写出来比较：左侧是 2 个 \(6j\) 符号的乘积，右侧是 3 个 \(6j\) 符号乘积再对内部边标签 \(j\) 带权重 \(d_j\) 求和。移项后两边相等的条件恰好是五边形恒等式：每个 pentagon identity 的等式两边各含 2 个与 3 个 \(6j\) 符号，与一个内部标签的带权求和。换言之：
Pachner \(2\)--\(3\) move 的不变性 \(\Longleftrightarrow\) pentagon identity。
这就是第 2 节说"五边形恒等式是 Pachner move 的代数翻译"的精确含义，也是练习 3 的内容。
\(1\)--\(4\) move（一个四面体变四个）。 在一个四面体内部加一个顶点、连到四个顶点，把它分成四个。move 在求和中引入一个新的内部顶点（归一化因子 \(\mathcal N\) 里的 \(\mathcal D^2\) 幂随之改变）和四条新的内部边。把四条新边的求和逐步做掉：先用一次 \(6j\) 符号的正交关系消去一对求和，重复三次后右侧坍缩回左侧的单个 \(6j\) 符号，剩下的 \(\mathcal D^2\) 因子正好被 \(\mathcal N\) 的变化抵消。因此：
Pachner \(1\)--\(4\) move 的不变性 \(\Longleftrightarrow\) quantum-dimension 加权的正交关系 + 归一化 \(\mathcal N\) 的选取。
两条 move 都不变，而 Pachner 定理说这就够了，所以 \(TV_r(M)\) 是良定义的拓扑不变量。值得强调证明的结构：不变性不是逐个流形验证的，而是归约为有限多条代数恒等式；这也是为什么任何满足同样公理的融合范畴数据都能造出自己的状态和不变量。
3.3 经典瓶颈¶
这个定义能直接当算法用吗？数一数求和的项数：三角剖分有 \(E\) 条边（对三维三角剖分 \(E\asymp T\)，由每个四面体 6 条边、每条边被常数个四面体共享可知），每条边有 \(r-1\) 个候选标签，故着色总数为 \((r-1)^{E}\) 量级——即使 \(r\) 是常数，也是关于 \(T\) 的指数。逐项检查 admissibility 并累加只是暴力枚举，关于输入大小是指数时间。
能不能更聪明？精确计算三维流形不变量被认为是困难的：同一族量（如 Jones 多项式在根值处的求值、三维流形不变量的精确值）普遍落在 \(\#P\)-hard 的难度量级，而 \(\#P\) 问题被认为连经典多项式时间随机算法都无法企及。本章导言里的原则在这里再次生效：一个 #P-hard 的精确量，不会因为存在某种加性量子估计就变得普遍易算——量子算法逼近的是一个特定归一化尺度下的加性近似，这与精确求值、也与任意精度逼近都不是一回事。记住这条保留条款，第 7 节还会回到它。
4. TQFT Hilbert 空间与 Heegaard 振幅¶
4.1 从状态和到算子：核心直觉¶
状态和写法把 \(M\) "摊平"成一堆局部数相乘再求和，没有留出任何"演化"的结构。换一种看法：把三维流想象成二维空间加一维时间的 \((2+1)\) 维物理系统，那么一个三维流形 \(M\) 可以被切开成"空间切片"（曲面）和"时间演化"（曲面之间的三维 cobordism）。一个 \((2+1)\) 维 TQFT 就是把这套图像公理化的规则：
给每张闭曲面 \(\Sigma\) 分配一个有限维 Hilbert 空间 \(V_r(\Sigma)\)（"该曲面上 anyon 系统的态空间"）；
给每张曲面的自同胚类 \(\varphi\in\mathrm{MCG}(\Sigma)\) 分配一个酉算子（投影表示，整体相位与 framing 约定有关）
给两个曲面之间的三维流形分配算子/态，使得"沿公共曲面粘合"对应于"算子复合"或"取内积"。
第三条是灵魂：TQFT 把几何粘合翻译成线性代数运算。一旦接受这条字典，Heegaard splitting 的算法含义立刻浮现——\(M=H_g\cup_\varphi H_g\) 说的是"一个 handlebody、经历演化 \(\varphi\)、再与另一个 handlebody 对接"，翻译成线性代数就是一个三明治式的矩阵元。
4.2 Handlebody 真空态与 Reshetikhin--Turaev 振幅¶
具体地，handlebody \(H_g\) 作为以 \(\Sigma_g\) 为边界的三维流形，通过 TQFT 规则选出 \(V_r(\Sigma_g)\) 中的一个特定态，称为真空态（vacuum/handlebody state） \(|\Omega_g\rangle\)。直觉：它对应"handlebody 内部没有任何 anyon 激发"的基态；在融合基下，它是所有内部融合通道都取真空标签 \(0\) 的那个基矢（第 5 节定义融合基后会看得更清楚）。
于是 Reshetikhin--Turaev 振幅（与 Turaev--Viro 紧密相关的另一族不变量）可以写成真空—演化—真空的重叠：
这个公式的来历正是上面的"粘合=内积"字典：第一个 \(H_g\) 制备 \(|\Omega_g\rangle\)，gluing homeomorphism \(\varphi\) 贡献酉算子 \(\rho_r(\varphi)\)，第二个 \(H_g\)（注意粘合时取向相反）贡献 bra 矢量 \(\langle\Omega_g|\)。
对相应的 doubled/unitary 范畴（Turaev--Viro 理论对应 Drinfeld center，而当输入范畴本身已是酉模范畴时，该构造退化为"正手性 \(\oplus\) 反手性"两份），Turaev--Viro invariant 与该振幅的模平方相关：
比例因子由归一化约定、genus \(g\) 与总量子维数 \(\mathcal D\) 决定——它是已知的、可经典计算的函数。物理图像上模平方很自然：Turaev--Viro 是"手性 + 反手性"两份理论的乘积，而反手性那份贡献振幅的复共轭。对算法的意义在于：只要能量子地估计一个矩阵元 \(a=\langle\Omega_g|\rho_r(\varphi)|\Omega_g\rangle\) 的模平方，再乘上这个已知归一化，就得到了 \(TV_r(M)\)。算法必须显式携带该归一化——后面讨论 BQP-hardness 的精度尺度时，这一点是定义问题实例的一部分。
一个健康性检查：取 \(M=S^3\)，它由 genus 任意（包括 \(g=0\)，\(S^2\) 上 \(V_r\) 是一维的）的平凡 splitting 给出，振幅就是相应的 modular \(S\) 矩阵元 \(S_{00}=1/\mathcal D\)。按标准归一化 \(TV_r(S^3)=1/\mathcal D^2\)，恰有 \(TV_r(S^3)=|S_{00}|^2\)。第 8 节的数值例子会在 genus 1 重新看到这个等式。
4.3 \(V_r(\Sigma_g)\) 有多大？¶
这个 Hilbert 空间的维数由 Verlinde 公式给出。我们不需要公式本身，只需要它的渐近行为：固定 \(r\)、令 \(g\) 增长时，
（差一个随 \(r\)、\(g\) 多项式变化的因子； genus 0、1 是退化情形）。也就是说，态空间随 genus 指数增长。这立刻解释了两件事：
为什么经典算法在 Heegaard 表示下同样指数：直接把 \(\rho_r(\varphi)\) 写成矩阵并计算，矩阵有 \(\mathcal D^{\Theta(g)}\) 行；
为什么量子算法有希望：指数大的 Hilbert 空间正是量子线路的拿手好戏——只要 \(\rho_r(\varphi)\) 能分解成局部门，就永远不必把矩阵写出来。
下一节的任务就是把"\(\rho_r(\varphi)\) 分解为局部门"这句话变成电路构造。
5. 量子算法：把 mapping class word 编译成电路¶
5.1 融合基：把指数大的态空间编码进量子比特¶
给曲面 \(\Sigma_g\) 选一个 pants decomposition（把曲面沿 \(3g-3\) 条简单闭曲线剪成 \(2g-2\) 条"裤子"=三孔球面），等价地选一个 trivalent spine。每条 pants 曲线携带一个 anyon 标签，每条裤子要求其三个边界标签满足融合可容许性；所有满足条件的标签赋值构成 \(V_r(\Sigma_g)\) 的一组标准正交基，称为融合基（fusion basis）：
基矢个数（即 \(\dim V_r(\Sigma_g)\)）虽随 \(g\) 指数增长，但每个基矢由 \(O(g)\) 个标签描述，每个标签只有常数 \(r-1\) 种取值——因此可以用 \(O(g\log r)\) 个量子比特编码一个标签串，并用一个关于 \(g\) 多项式大小的子程序标记可容许串。真空态 \(|\Omega_g\rangle\) 对应所有标签取 \(0\) 的基矢，制备它是平凡的。
5.2 三类局部 move¶
群 \(\mathrm{MCG}(\Sigma_g)\) 的每个生成元（Dehn twist、braiding、把手滑移等）在融合基下可以分解为有限个局部拓扑 move 的复合：
\(F\) move（重括号）：改变融合树的局部括号结构。它是只涉及常数个相邻标签的基变换，矩阵元是 quantum \(6j\) 符号——第 2 节的组合数据在这里以"门"的身份重新登场。五边形恒等式保证任意两条 \(F\) move 序列给出同一变换，所以 braiding/twist 的分解结果与分解方式无关。
\(R\) move / braiding（交换）：交换两个相邻融合通道，施加一个局部相位（braiding eigenvalue）。
Dehn twist（扭转）：沿某条曲线剪开扭转，在融合基下对该曲线标签 \(j\) 的 sector 施加 topological spin 相位 \(\theta_j\)（一个由范畴数据决定的单位根）。
关键观察：固定 \(r\) 时，标签集大小是常数 \(r-1\)，每个 move 只触及常数个标签，因此每个 move 是一个作用在常数量子比特上的常数尺寸门，其矩阵元（\(6j\) 符号、braiding 相位、\(\theta_j\)）都是可经典预先计算到任意精度的常数。
5.3 电路规模¶
设 gluing word \(\varphi\) 长 \(m\)。每个生成元沿一条曲线作用，把这条曲线"拉近"到 pants decomposition 的局部、执行局部 move、再拉回去，代价是关于 \(g\) 的多项式个 \(F/R\) 门（把远处曲线局部化的重括号序列长度至多是 \(O(g)\) 量级，具体幂次取决于模型细节）。因此整个
由一个 \(\operatorname{poly}(g,m)\) 大小的量子电路实现。这就是"关于 Heegaard 输入 \((g,m)\) 多项式"的精确含义——对比第 3.3 节关于 \(T\) 指数的着色枚举，两种表示下的难度景观完全不同。
5.4 Hadamard test 与采样复杂度¶
电路就绪后，剩下的是读出矩阵元
标准工具是 Hadamard test（第 3 章）：引入一个辅助比特，制备 \((|0\rangle+|1\rangle)/\sqrt2\)，执行受控-\(U_\varphi\)（控制端为辅助比特，目标端初态 \(|\Omega_g\rangle\)），再对辅助比特做 Hadamard 并测量。直接展开：
最后一步用了 \(H|0\rangle=(|0\rangle+|1\rangle)/\sqrt2\)、\(H|1\rangle=(|0\rangle-|1\rangle)/\sqrt2\)。辅助比特测得 \(0\) 的概率为
其中第二步展开范数、第三步用了 \(U_\varphi^\dagger\) 的矩阵元是 \(a^*\)。把受控-\(U_\varphi\) 换成"受控-\(U_\varphi\) 后接辅助比特相位门 \(S\)"（等价地在初态用 \(|0\rangle+i|1\rangle\)），同理得到 \(p_0'=\tfrac12(1-\operatorname{Im}\,a)\)。于是
每个概率 \(p\in\{p_0,p_0'\}\) 是单次测量的 Bernoulli 参数，用 \(K\) 次独立重复的经验频率 \(\hat p\) 估计，由 Hoeffding 不等式 \(\Pr[|\hat p-p|\ge\delta]\le 2e^{-2K\delta^2}\)，取 \(K=\Theta(1/\delta^2)\) 即以常数置信度把 \(p\) 估到 \(\pm\delta\)，从而把 \(\operatorname{Re}\,a\)、\(\operatorname{Im}\,a\) 各估到 \(\pm 2\delta\)。令 \(\varepsilon=2\delta\)：用
次电路运行，得到 \(a\) 的加性 \(\varepsilon\) 估计 \(\hat a\)。最后用 \(|\hat a|^2\) 估计 \(|a|^2\) 并乘上第 4.2 节的已知归一化，得到 \(TV_r(M)\) 的加性估计。
5.5 误差传播：从 \(a\) 到 \(|a|^2\)¶
模平方这一步会放大误差吗？写 \(a=\hat a+\eta\)、\(|\eta|\le\sqrt2\,\varepsilon\)（实部虚部各 \(\varepsilon\)），则
结论有两层：
绝对误差从 \(O(\varepsilon)\) 变为 \(O(|a|\varepsilon+\varepsilon^2)\)——仍是加性误差，量级不变；
但当 \(|a|\) 本身很小时，这个加性误差相对于 \(|a|^2\) 却很大：要做到相对误差，需要 \(\varepsilon\lesssim|a|\)，即采样数 \(1/|a|^2\)。而由第 4.3 节，典型振幅随 genus 指数缩小（真空矩阵元本身带 \(\mathcal D^{-\Theta(g)}\) 的尺度），所以相对逼近一般需要指数采样——这正是"量子算法给出的是加性近似"这句保留条款的技术根源，也是第 7 节 BQP-hardness 必须把归一化尺度写进问题定义的原因。
5.6 复杂度逐项清单¶
把整条流水线的代价摊开，每个因子各有着落：
编码：\(O(g\log r)\) 量子比特；\(r\) 固定时为 \(O(g)\)。
电路：每个生成元 \(\operatorname{poly}(g)\) 个局部门，共 \(m\) 个生成元，电路规模 \(\operatorname{poly}(g,m)\)；每个门的常数矩阵元可经典预计算。
采样：\(\Theta(1/\varepsilon^2)\) 次独立运行（Hoeffding），每次运行执行一遍上述电路。
总计：\(\operatorname{poly}(g,m)/\varepsilon^2\)，加上可经典计算的归一化因子。
于是：对 Heegaard splitting 输入，\(TV_r(M)\) 的加性 \(\varepsilon\) 估计在量子多项式时间（关于 \(g\)、\(m\)、\(1/\varepsilon\)）内完成。 注意 \(1/\varepsilon^2\) 意味着 \(\varepsilon\) 取 \(1/\operatorname{poly}\) 仍高效、取指数小则不再高效——这把"哪类逼近是容易的"精确钉在了加性、\(1/\operatorname{poly}\) 精度的格子上。
6. 为什么该近似是量子通用的¶
上一节给出了一个多项式量子算法。Alagic、Jordan、König 与 Reichardt（Zoo 编号 129）证明的其实是反方向的、强得多的陈述：在上述归一化尺度下加性逼近 \(TV_r(M)\) 这个问题，任何经典多项式算法若能解决它，就能解决一切 BQP 问题——即该问题是 BQP-complete 的（"在 BQP 中"由第 5 节的算法给出，"BQP-hard"由本节概述的编码给出）。
证明思路（定性）。 两个要件：
表示足够稠密。 在适当固定的 level/范畴下（论文指定具体选择），\(\mathrm{MCG}(\Sigma_g)\) 的 TQFT 表示在相应的（射影）酉群中足够稠密——粗略说，Dehn twist 生成的酉群像大到可以逼近任意单比特/两比特门。这与"任意子门集通用"的证明同类：已有的 Solovay--Kitaev 类结果把"稠密"升级为"用多项式长度 word 逼近任意酉"。
电路编译成 gluing word。 给定任意量子电路 \(C\)（\(n\) 比特、多项式规模），经典地选一个 genus 与 \(n\) 相称的曲面，把 \(C\) 的每个通用门用要件 1 逼近成一段 mapping class word，顺序拼接得到 \(\varphi_C\)。整个编译是经典多项式时间的。由构造，\(C\) 的接受振幅（或接受概率）被嵌入
或其模平方之中——具体说，编译安排得使该矩阵元与 \(C\) 的接受概率相差一个已知的归一化因子。
现在把两块拼起来：若有一个（哪怕是经典的）算法能在论文指定的 normalization 尺度内加性逼近 \(TV_r(M_C)\)，把它作用于编译输出的流形 \(M_C\)，就能读出 \(C\) 的接受概率，从而判定任意 BQP 语言。故该逼近问题 BQP-hard。
保留条款（务必逐条记牢）。 证明 BQP-hard/complete 的是以下三者同时成立的问题版本：
特定 level：\(r\) 取论文指定的常数（使表示稠密那一档），不是"对所有 \(r\)"；
Heegaard splitting 输入：输入是 \((g,\varphi)\) 的 word，不是任意三角剖分；
与 genus 相关的非平凡加性精度：误差尺度随 genus（经 \(\mathcal D\)）缩小到与典型振幅同阶，这是问题定义的一部分，不是算法偷懒。
因此该结果不表示：任意 triangulation 上的所有 Turaev--Viro 参数都能高效相对逼近（第 5.5 节已说明相对逼近为何一般需要指数采样）；也不直接解决三维流形 homeomorphism 问题——它只是说"在严格指定的近似意义下，这个不变量恰好和量子计算一样难算"。这与本章导言对 #P-hard 量的一般告诫完全一致。
7. Spin network 视角¶
还有第三种等价语言，把前两种拧在一起，也是 Zoo 编号 114、115 两篇工作的母语。
取三角剖分的对偶 2-skeleton，画成一张三价图：每条对偶边对应三角剖分的一条边、携带表示标签 \(j_e\)，每个顶点（对偶于四面体）对应一个 intertwiner——把三条进来的表示耦合出去的 invariant 张量，数值上就是 quantum \(6j\) 符号。整幅带标签的图称为 q-deformed spin network。于是 Turaev--Viro 状态和可读作"对 spin network 所有标签赋值的相干求和"，而局部 recoupling（重括号）就是 \(F/6j\) move——与第 5.2 节融合基下的门是同一代数的两种画法。
这条字典的用处在于把两篇参考文献安放进图景：
Garnerone--Marzuoli--Rasetti（Zoo 编号 114） 直接以 spin network 为工作介质，构造了处理若干三维流形拓扑不变量的量子 "spin-network automaton"：态空间按 spin-network 基编码，不变量的局部因子由量子线路相干求值与累加。
Kauffman--Lomonaco（Zoo 编号 115） 系统建立了 q-deformed spin network、knot 多项式与 anyonic 拓扑量子计算之间的对应，说明任何子计算在数学上等价于对 spin network 的相干重括号化。
两者与第 5 节的 Heegaard 振幅算法共享同一个 recoupling 代数（同一套 \(6j\) 符号、同一个五边形恒等式），差别只在把哪一个对象当作"基态"、哪一个对象当作"演化"：Heegaard 方案以 handlebody 真空为基、mapping class word 为演化；spin-network 方案直接以图为基、局部 move 为演化。理解这一层等价性，就读懂了这三篇文献其实讲的是同一件事的三副面孔。
8. 一个 genus-1 例子（完整手算）¶
最小的非平凡情形 \(g=1\)：曲面 \(\Sigma_1\) 是环面 \(T^2\)，其 mapping class group 是由两个生成元生成的（射影）模群，
满足射影关系 \(S^2=\mathrm{id}\)、\((ST)^3=\mathrm{id}\)（等号在 \(\mathrm{PSL}(2,\mathbb Z)\) 中理解；提升到 \(\mathrm{SL}(2,\mathbb Z)\) 会差中心元，对应 framing 相位）。几何上，\(T\) 是沿环面一条本原曲线的 Dehn twist，\(S\) 交换环面的两条基本环路。相应的 TQFT 表示 \(\rho_r\) 把抽象的 \(S,T\) 映为 \(V_r(T^2)\) 上的 modular \(S\)、\(T\) 矩阵——这正是"曲面的对称性变成 Hilbert 空间上的酉矩阵"的最小实例。genus-1 的 handlebody 是实心环，真空态 \(|\Omega_1\rangle=|0\rangle\) 即真空 anyon 标签对应的基矢。
一般形状。 genus-1 的 Heegaard gluing 产生所谓 lens space 及其近亲：任一 \(\varphi\) 可写成
相应不变量是 modular \(S,T\) 矩阵相应真空矩阵元 \(\langle0|\,\rho_r(\varphi)\,|0\rangle\) 的函数。量子算法逐个实现 \(S,T\) 门、按 word 顺序执行、再用 Hadamard test 估计这个矩阵元——而不是枚举 triangulation 的全部 coloring。
数值实例：\(r=3\)（即 \(SU(2)\) level \(k=r-2=1\)）。 此时标签集只有 \(\{0,\tfrac12\}\)，\(\dim V_3(T^2)=2\)，全部数据都能手算：
量子维数：\(d_0=1\)，\(d_{1/2}=\dfrac{\sin(2\pi/3)}{\sin(\pi/3)}=1\)，故 \(\mathcal D^2=1+1=2\)，与第 2 节公式 \(\mathcal D^2=\dfrac{r}{2\sin^2(\pi/r)}=\dfrac{3}{2\cdot(3/4)}=2\) 一致。
Modular \(S\) 矩阵（由标准公式 \(S_{ab}=\sqrt{\tfrac{2}{k+2}}\sin\tfrac{\pi(a+1)(b+1)}{k+2}\)，\(a,b\in\{0,1\}\) 为 \(2j\) 指标）：\(S=\dfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\)——恰好就是 Hadamard 门。
Modular \(T\) 矩阵：topological spin \(h_{1/2}=\tfrac{j(j+1)}{k+2}=\tfrac14\)，故 \(\theta_{1/2}=e^{2\pi i h_{1/2}}=i\)，即 \(T=\begin{pmatrix}1&0\\0&i\end{pmatrix}\)（至多差一个来自 framing 的整体相位，不影响模平方）。
例 1：\(\varphi=\mathrm{id}\)。 平凡粘合给出 \(M=S^2\times S^1\)（genus-1 的最简单 splitting）。振幅 \(\langle0|I|0\rangle=1\)，无任何计算——对应"电路为空、Hadamard test 恒输出 0"。
例 2：\(\varphi=S\)。 交换两条环路的粘合给出 \(S^3\)（genus-1 Heegaard splitting 下的三维球面）。振幅
对照第 4.2 节的健康性检查：标准归一化下 \(TV_3(S^3)=1/\mathcal D^2=1/2\)，恰为振幅模平方——归一化因子在这个例子里是 1。手算与理论严丝合缝。
例 3：\(\varphi=ST^pS\)（演示 word 逐个执行）。 这是 \(ST^{p_1}ST^{p_2}\cdots\) 形状的最短非平凡实例。先算矩阵元：
第二步用了 \(S_{0b}=S_{b0}=1/\sqrt2\) 与 \(T^p=\mathrm{diag}(1,i^p)\)。于是
三种取值分别对应"电路输出恒定、干涉相长、干涉相消"——一次 Hadamard test 采样就能以 \(1/\varepsilon^2\) 次运行把三者区分开。这个例子的教学要点不在流形本身，而在看清算法的机械过程：word 的每个字母是一个 \(2\times2\) 门，矩阵元是门的乘积的真空元，量子线路做的正是把这个乘积相干地算出来。genus 更大、标签更多时，唯一的差别是单个门作用的标签数变多、word 变长——第 5 节的 \(\operatorname{poly}(g,m)/\varepsilon^2\) 清单逐项原样适用。
9. 小结¶
小结。
Turaev--Viro invariant 是 triangulation 上 quantum dimensions 与 quantum \(6j\) symbols 的状态和；其拓扑不变性归约为五边形恒等式（\(2\leftrightarrow3\) move）与量子维数加权的正交关系（\(1\leftrightarrow4\) move）。
直接按定义求和有关于 \(T\) 指数多的着色项，精确计算落在 #P-hard 的难度量级，经典上不可行。
Heegaard splitting 把同一不变量改写为 TQFT mapping-class 酉表示的真空振幅模平方（比例是已知归一化），而 TQFT 的"粘合=内积"字典是这一切换的核心。
\(F\) move、\(R\) move、Dehn twist 都是常数尺寸的局部门，长度 \(m\) 的 gluing word 在 genus \(g\) 曲面上实现为 \(\operatorname{poly}(g,m)\) 电路；Hadamard test 以 \(\Theta(1/\varepsilon^2)\) 采样给出加性 \(\varepsilon\) 估计。
在特定 level、Heegaard 输入、与 genus 相称的加性归一化下，该逼近问题是 BQP-complete 的（Zoo 编号 129）；但这不能扩大成对任意 triangulation 参数的相对逼近，也不直接解决三维流形 homeomorphism 问题。
练习题¶
练习 1【三角剖分与 Heegaard 分解】（→ 第 1 节）
写出三角剖分与 Heegaard splitting 两种输入各自的规模度量（\(T\) 与 \((g,m)\)），并指出粘合映射 \(\varphi\) 属于哪个群、这个群由哪类生成元生成。
解释为什么"\(TV_r(M)\) 可在多项式时间内估计"这类陈述必须注明是关于 \(T\) 还是关于 \((g,m)\)，并举出两种表示的大小可以相互相差巨大的情形。
练习 2【量子维数与 quantum 6j 符号】（→ 第 2 节）
取 \(r=4\)：写出标签集，计算 \([2]_q\)、\([3]_q\) 与 \(d_{1/2}\)、\(d_1\)，并用 \(\mathcal D^2=\dfrac{r}{2\sin^2(\pi/r)}\) 验证 \(\mathcal D^2=\sum_j d_j^2\)。
写出融合可容许性的三个条件，并判断 \(r=3\) 时三元组 \((\tfrac12,\tfrac12,\tfrac12)\) 与 \((\tfrac12,\tfrac12,0)\) 是否可容许。
提示：\(r=3\) 时 \(r-2=1\)；注意 \((\tfrac12,\tfrac12,\tfrac12)\) 同时违反整数性与截断两个条件，而 \((\tfrac12,\tfrac12,0)\) 还需逐条核对三角形规则。
练习 3【Turaev--Viro 状态和与 Pachner 不变性】（→ 第 3 节）
写出状态和公式的四个组成部分（求和范围、边上的量子维数因子、四面体的 \(6j\) 因子、归一化 \(\mathcal N\)），并说明 \(\mathcal N\) 在哪一类 Pachner move 下发挥作用。
设三角剖分有 \(E\asymp T\) 条边、\(r\) 固定，估算 admissible coloring 的数量级，并解释 Pachner 定理为什么能把不变性证明归约为只核对两类 move。
把 Pachner \(2\)--\(3\) move 两侧的状态和局部因子完整写出来（左侧 2 个四面体、右侧 3 个四面体加一条内部边），指出把内部边标签求和并利用融合可容许性后，两边相等的等式为什么逐条就是五边形恒等式。说明每个 pentagon identity 中的五个 \(6j\) 符号分别对应 move 中的哪几个四面体。
提示：右侧对新增内部边标签 \(j\) 的求和带权重 \(d_j\)，与五边形恒等式一边的带权求和逐项对应。
练习 4【TQFT 字典与真空振幅】（→ 第 4 节）
列出 \((2+1)\) 维 TQFT 的三条分配规则，并把 Heegaard splitting \(M=H_g\cup_\varphi H_g\) 翻译成"真空—演化—真空"的矩阵元。
解释 \(TV_r(M)\propto|RT_r(M)|^2\) 中模平方的物理来源，并说明比例因子为什么是已知的、可经典计算的——以及算法为何必须显式携带它。
（两种表示的状态空间）设三角剖分有 \(T\) 个四面体，level \(r\) 固定。(a) 着色求和的状态空间大约多大？(b) 若同一流形用 genus \(g\) 的 Heegaard splitting 给出，融合基的状态空间大约多大（用 \(\mathcal D\) 表示）？(c) 量子算法绕开了两者中的哪一个、如何绕开？
提示：(a) 每条边约 \(r-1\) 个候选标签、共 \(E\asymp T\) 条边；(b) 用 Verlinde 公式 \(\dim V_r(\Sigma_g)=\Theta(\mathcal D^{2(g-1)})\)。
练习 5【融合基与局部门编译】（→ 5.1 节）
描述融合基：pants decomposition 有多少条曲线、每条曲线携带什么、可容许性如何筛选基矢；说明为什么每个基矢只需 \(O(g\log r)\) 个量子比特编码、真空态为何平凡制备。
固定 \(r\)，解释 \(F\) move、\(R\) move、Dehn twist 为什么都是作用在常数量子比特上的常数尺寸门，并据此推导长度 \(m\) 的 gluing word 在 genus \(g\) 曲面上的电路规模为 \(\operatorname{poly}(g,m)\)。
提示：每个生成元沿曲线作用时，先用 \(O(g)\) 量级的重括号把作用曲线"拉近"到局部；五边形恒等式保证分解结果与路径无关。
练习 6【Hadamard test 与误差传播】（→ 5.4 节）
从 Hadamard test 末态的展开推导 \(p_0=\tfrac12(1+\operatorname{Re}\,a)\)，并说明如何改造线路（在受控-\(U_\varphi\) 后接辅助比特相位门）以估计 \(\operatorname{Im}\,a\)。
（采样）第 5.4 节用 Hoeffding 不等式得到 \(K=\Theta(1/\varepsilon^2)\) 次运行把 \(\operatorname{Re}\,a\) 估到 \(\pm\varepsilon\)。若要求置信度为 \(1-\delta_{\rm conf}\) 而非某个常数，请推出 \(K\) 关于 \(\varepsilon\) 与 \(\delta_{\rm conf}\) 的完整表达式，并说明为什么对 \(\delta_{\rm conf}\) 的依赖只是对数的。
（误差传播）设 \(|a|=2^{-n}\)。要把 \(|a|^2\) 估计到相对误差 \(10\%\)，用第 5.5 节的界推出 \(\varepsilon\) 需要多小、采样数 \(K\) 需要多大（用 \(n\) 表示）。据此解释"相对逼近一般需要指数采样"。
提示（题 2）：由 \(2e^{-2K\delta^2}\le\delta_{\rm conf}\) 解出 \(K\)，注意 \(\varepsilon=2\delta\)。 提示（题 3）：相对误差 \(10\%\) 要求 \(\varepsilon\) 与 \(|a|\) 同阶，代入 \(K=\Theta(1/\varepsilon^2)\)。
练习 7【BQP 通用性与保留条款】（→ 第 6 节）
逐条列出使"加性逼近 \(TV_r\)"成为 BQP-complete 的三个前提（level、输入表示、精度尺度），并指出"该问题在 BQP 中"与"BQP-hard"两半分别由哪一节的构造给出。
（归一化尺度）用第 4.3 节 \(\dim V_r(\Sigma_g)=\Theta(\mathcal D^{2(g-1)})\) 与一个典型酉矩阵元振幅约 \(1/\sqrt{\dim V}\) 的启发式，说明为什么"有意义的"加性误差 \(\varepsilon\) 必须随 \(g\) 记录（而不是取常数），并据此解释 Zoo 编号 129 把 normalization 写进问题定义的必要性。
提示：\(1/\sqrt{\dim V_r(\Sigma_g)}=\mathcal D^{-(g-1)}\)，随 \(g\) 指数缩小。
练习 8【Genus-1 手算实例】（→ 第 8 节）
在 \(r=3\) 时写出标签集、量子维数 \(d_0\)、\(d_{1/2}\)、\(\mathcal D^2\) 与 modular \(S\)、\(T\) 矩阵，并验证例 2 中 \(TV_3(S^3)=1/\mathcal D^2=1/2\) 恰为振幅模平方。
（手算）在 \(r=3\) 的 genus-1 例子中，取 \(\varphi=T\)。(a) 计算 \(a=\langle0|T|0\rangle\) 与 \(|a|^2\)；(b) 取 \(\varphi=ST\)，计算 \(|a|^2\) 并对照第 8 节例 3 的 \(p=1\) 行；(c) 说明若只知道 \(|a|^2\) 的 \(\pm0.1\) 加性估计，你能区分例 3 中 \(p\equiv0\) 与 \(p\equiv2\pmod4\) 两种情形吗？
提示：\(T=\operatorname{diag}(1,i)\)；\(ST|0\rangle=S|0\rangle\)，而 \(S\) 的第一行元素都是 \(1/\sqrt2\)。
参考文献¶
Zoo 编号 129：Alagic、Jordan、Koenig 与 Reichardt, Approximating Turaev--Viro 3-Manifold Invariants Is Universal for Quantum Computation.
Zoo 编号 114：Garnerone、Marzuoli 与 Rasetti, Efficient Quantum Processing of 3-Manifold Topological Invariants.
Zoo 编号 115：Kauffman 与 Lomonaco, q-Deformed Spin Networks, Knot Polynomials and Anyonic Topological Quantum Computation.