# 量子结与链环不变量：Braid 表示、Jones 多项式与 Khovanov 同调

Jones 多项式把结图的拓扑信息编码为一个 Laurent 多项式：逐项展开会指数爆炸，精确计算在大多数求值点上落在 $\#\mathsf{P}$-hard 的难度量级。然而在特定的单位根处，同一个数值可以改写成 braid group 酉表示的矩阵元或 Markov trace——而“估计一个酉矩阵元”正是量子线路（配合 Hadamard test）的母语。本课从零开始推导这条链路：先讲清结不变量为什么难算，再把结代数化为 braid word 与 Temperley--Lieb 代数，然后在单位根上构造 path model 酉表示，得到 Aharonov--Jones--Landau（AJL）的多项式时间量子算法；最后讨论两处“完备性”边界——plat closure 的加性近似是 BQP-complete、trace closure 的归一化迹估计是 DQC1-complete——以及把 Jones “范畴化”之后的 Khovanov 同调在 2025 年出现的量子算法与它的适用条件。

**为什么值得关心？** 结不变量是区分不同结与链环的第一道筛子：若两个链环的不变量不同，它们一定不同痕。判定“两个结是否等价”（结问题）在经典上是可判定的，但已知的通用判定过程（如 Haken 的 normal surface 理论）复杂度高得难以使用；而不变量这一侧，精确计算又普遍 $\#\mathsf{P}$-hard。量子算法给出的第三条路是**特定归一化尺度下的加性近似**——它既不是精确值，也不是相对误差，理解“这到底买到了什么”是本课贯穿始终的主线，也是本章 index 页反复强调的原则：一个 $\#\mathsf{P}$-hard 精确量不因存在某种加性量子估计就变得普遍易算。

**历史脉络（与文末参考文献对应）。** 结不变量一侧：Reidemeister 于 1926 年证明同一链环的任意两张结图可由三类局部移动互变，这给出了“图上计算不变量”的合法性；Alexander 于 1928 年给出第一个多项式不变量（他的辫表示定理则早在 1923 年，见第 2.2 节）；Jones 于 1984 年在完全不同的语境（von Neumann 代数的子因子理论）中发现了以他命名的新多项式，并因此获得 Fields 奖；Temperley 与 Lieb 早在 1971 年研究冰模型传递矩阵时就写下了后来以他们命名的代数，Kauffman 于 1987 年用它给出 Jones 多项式的括号演算——本课第 3 节的整套计算就来自这条路线。物理一侧：Witten 于 1989 年指出 Jones 多项式是 Chern--Simons 拓扑量子场论中 Wilson 圈的期望值，Reshetikhin--Turaev 随后给出了严格的数学构造；Freedman、Kitaev、Larsen 与 Wang 在 2000 年前后证明了这类 TQFT 与量子计算可以互相模拟——这既预示了拓扑量子计算（用 anyon 的编织做通用量子门），也隐含了“逼近 Jones 多项式与量子计算一样难”的完备性结论。算法一侧：Aharonov--Jones--Landau 于 2005 年（STOC 2006）避开 TQFT、直接用 Temperley--Lieb 代数的 path model 表示，写出了显式的多项式时间量子算法（Zoo 2、4、41、42 对应这条线）；Shor 与 Jordan 随后证明某些 trace closure 的 Jones 近似在 DQC1 模型中完备（Zoo 83）；HOMFLY 与 quantum-double 型链环不变量有类似的表示论算法（Zoo 93、174）；与 Tutte/Potts 配分函数的联系见 Zoo 3 及本章 [配分函数量子算法](partition-functions.md) 一课。2025 年，Schmidhuber 等人给出了第一个 Khovanov 同调的量子算法（Zoo 510--511），其核心是把同调秩的计算化为 Hodge Laplacian 近零谱质量的估计。

**前置知识。** 本课假定读者已完成本站第 1--8 章：量子态与测量、Hadamard 门、Grover 搜索、相位估计与振幅估计、基本的线性代数（内积、投影、酉算子）。Hadamard test 与 Hoeffding 不等式会在这里自足地推导，不需要回头翻第 3 章；但振幅估计只引用结论“$O(1/\epsilon)$ 次相干调用给出加性 $\epsilon$ 估计”。拓扑一侧不要求任何先验知识：结、链环、braid、Reidemeister 移动都会就地定义。

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

1. **[Kauffman 括号与 Jones 多项式](#kauffman-bracket-jones)**——能写出 Kauffman 括号的三条规则并计算简单链环的括号值，解释 writhe 补偿因子 $(-A)^{-3w(D)}$ 为何把括号修补成链环不变量。
2. **[辫群与两种闭合](#braid-closures)**——能写出辫群的生成元与定义关系，并比较 trace closure 与 plat closure 对应的“迹”与“矩阵元”两种读出方式。
3. **[Temperley--Lieb 代数与表示定理](#tl-algebra-representation)**——能用图示演算验证三条 TL 关系，并推导 $\rho_A(\sigma_i)=AI+A^{-1}e_i$ 成为辫群表示的充要条件 $d=-(A^2+A^{-2})$。
4. **[单位根与 path model 酉表示](#unitary-path-model)**——能证明酉性引理 $UU^\dagger=I+(A^2+A^{-2}+d)e$，并解释在 $A=t^{-1/4}$、$d=-2\cos(\pi/k)$ 处如何用路径图 $A_{k-1}$ 与 Perron--Frobenius 权重构造酉的路径表示。
5. **[Hadamard test 与加性近似](#hadamard-test-additive-approximation)**——能推导 Hadamard test 的读出公式并换算 $\Theta(1/\epsilon^2)$ 与 $O(1/\epsilon)$ 两种采样复杂度，解释“相对于归一化 $C(b,k)$ 的加性近似”的确切承诺及其误差尺度。
6. **[Markov trace 与 DQC1](#markov-trace-dqc1)**——能解释 Markov trace 为何取终点 $\lambda$ 权重的形状，比较提纯与两阶段抽样两条实现路线并推导两阶段误差的参数平衡。
7. **[手算例子：Hopf 链环与三叶结](#worked-example-k6)**——能沿“TL 展开—闭合数圈—writhe 换元”的流程独立算出 Hopf 链环与三叶结的 Jones 值，并说明量子算法逼近的正是这些数值。
8. **[范畴化：Khovanov 同调](#khovanov-homology)**——能描述 Khovanov 链群与边缘算子的构造，解释分次 Euler 特征标如何恢复 Jones 多项式、同调为何携带严格更多的信息，以及秩的加性近似的三档难度阶梯。

:::

## 1. 问题从哪里来：结、链环与 Jones 多项式

### 1.1 结与链环

**结 (knot)** 是三维空间 $\mathbb R^3$（或三维球面 $S^3$）中一条自身不相交的闭曲线；**链环 (link)** 是若干条互不相交的闭曲线的并。两个链环**等价**（同痕，ambient isotopic），如果其中一个可以通过连续变形（曲线始终不自交、互不穿透）变成另一个。最简单的结是未打结的圆周，称为**平凡结 (unknot)**；最简单的非平凡结是三叶结 (trefoil)，最少需要三个交叉才能画出。

要把链环交给算法，必须先**拍一张二维照片**：取一个投影方向，把链环投影到平面上，并在每个交叉处记录哪条线在上方。这样得到的四价平面图称为**结图 (knot diagram)**；一张结图的规模用它包含的交叉数 $c$ 衡量。同一张图里“谁上谁下”是投影的真实信息，而“交叉的位置与连法”则依赖于投影方向——Reidemeister 定理（1926）把这些自由度完全刻画清楚：

> **定理 (Reidemeister)。** 同一个链环的任意两张结图，可以通过反复施加以下三类**局部**移动互相变换；反之，能如此互变的两张图代表同一个链环。
>
> - **R1**：增删一个“卷”（一段线自己跨过自己形成的单个交叉）；
> - **R2**：把一条压在另一条上的两平行线段整体滑走（同时增删两个交叉）；
> - **R3**：三段线之间的三角形滑动（交叉数不变，只改变哪个交叉在左边）。

这条定理的意义是算法性的：**任何“逐交叉计算的图泛函”只要在 R1、R2、R3 下不变，就是链环的不变量**。后文的 Kauffman 括号正是这样被逐条验证的。

(kauffman-bracket-jones)=
### 1.2 Kauffman 括号与 Jones 多项式

**Kauffman 括号 (Kauffman bracket)** $\langle D\rangle$ 是定义在（无向）结图 $D$ 上、取值于 $\mathbb Z[A,A^{-1}]$ 的函数，由三条规则完全确定：

1. **归一化**：$\langle\bigcirc\rangle = 1$（无交叉的圆周取值 $1$）；
2. **脱圈规则**：$\langle D\sqcup\bigcirc\rangle = d\,\langle D\rangle$，其中 $d = -A^2 - A^{-2}$，$D\sqcup\bigcirc$ 表示 $D$ 与一个不相交的圆圈之并；
3. **展开规则（skein 关系）**：在每个交叉处，
   $$
   \left\langle\ \text{交叉}\ \right\rangle = A\,\left\langle\ \text{平直型平滑}\ \right\rangle + A^{-1}\,\left\langle\ \text{转折型平滑}\ \right\rangle ,
   $$
   即把该交叉的四个端点两两重连：一种重连方式是“两条竖线”（平直型），另一种是“上弧接上弧、下弧接下弧”（转折型）。哪种平滑配 $A$、哪种配 $A^{-1}$，由交叉处上方线段的旋向决定；不同教材的约定可能恰好交换 $A$ 与 $A^{-1}$（因此交换了链环的两种手性），本课固定一种约定，结论不受影响。

反复应用规则 3，可以把任何结图化到没有交叉的情形，再用规则 1、2 读出 $d$ 的幂——所以括号总等于 $d$ 的幂的整系数组合，是一个 Laurent 多项式。但它是链环不变量吗？逐条对照 Reidemeister 移动（第 3.3 节将把这些验证代数化）会发现：

- **R2、R3 下不变**：局部计算恰好化为 Temperley--Lieb 代数的恒等式（第 3 节的主题）；
- **R1 下会差一个因子**：单个卷的括号是 $-A^{\pm3}$ 而不是 $1$（第 8 节将实际算出）。

修补办法是经典的：给结图 $D$ 定义**拧数 (writhe)** $w(D)$ 为全部交叉的带号总和（每个交叉按“右手拧”记 $+1$、“左手拧”记 $-1$），然后带上一个补偿因子。定义

$$
f_D(A) := (-A)^{-3w(D)}\,\langle D\rangle .
$$

一个卷会同时让 $w$ 变化 $\pm1$、让 $\langle D\rangle$ 乘上 $(-A)^{\mp 3}$（这正是 R1 失败的形态），两者恰好相消；R2 不改变 $w$ 且括号不变；R3 两者都不变。因此 $f_D(A)$ 在全部三类移动下不变，是链环不变量。以 $t = A^{-4}$ 换元，就得到 **Jones 多项式**：

$$
V_L(t) := f_D(A)\big|_{A = t^{-1/4}} .
$$

它也等价地由 Jones 原始的 skein 关系 $t^{-1}V_{L_+} - t\,V_{L_-} = (t^{1/2}-t^{-1/2})V_{L_0}$（配合 $V_{\bigcirc}=1$）定义，其中 $L_+,L_-,L_0$ 是只在同一个交叉处取三种不同处理的图。对多分量链环，$V_L\in\mathbb Z[t^{\pm 1/2}]$（半整数幂是正常的）；对结（单分量）则是 $t$ 的整幂 Laurent 多项式。两个基本值值得记住：$V_{\text{unknot}} = 1$，二分量平凡链环 $V = -t^{1/2}-t^{-1/2}$（第 8 节会顺带验证后者）。

### 1.3 经典算法能做到什么程度

**精确计算的指数瓶颈。** 按定义计算括号：$c$ 个交叉每个有两种平滑方式，展开成一棵深度为 $c$ 的二叉树，叶子数 $2^c$，每个叶子是若干不相交圆圈之并、其括号是 $d$ 的幂。这个“skein 树”算法的时间是 $\Theta(2^c)$：关于交叉数指数。动态规划可以省掉重复子树，但对一般输入仍然指数。

**不能指望多项式精确算法。** Jones 多项式与图论的 Tutte 多项式血脉相连：对交错结，Jones 在 $t$ 处的值可以用平面图的 Tutte 多项式在相应点读出（媒介构造见本章 [配分函数量子算法](partition-functions.md) 第 5 节）。而 Jaeger--Vertigan--Welsh 的一族结果表明，Tutte 多项式在大多数固定点上的精确求值是 $\#\mathsf{P}$-hard 的；相应地，Jones 多项式在大多数固定求值点上的精确计算也被证明（或普遍相信，视具体点集而定）落在同样的难度量级。只有少数特殊点（如 $t=\pm1$ 等退化情形）已知有多项式时间经典算法。本章反复出现的告诫在这里原样适用：$\#\mathsf{P}$-hard 的精确量不会被任何通用多项式算法（经典或量子）解决。

**近似怎么办？** 经典侧对这类拓扑量缺少通用的随机近似格式（对比：铁磁 Potts 配分函数有 FPRAS，但那是“正权重、可混合”的结构带来的）。量子侧的机会在于：把不变量改写成**酉算子的矩阵元**，矩阵元可以用 Hadamard test 以 $\Theta(1/\epsilon^2)$ 次采样（或振幅估计的 $O(1/\epsilon)$ 次）估计到加性 $\epsilon$。注意这个承诺的形状：**加性、相对于某个自然尺度**。若该尺度本身随输入指数增长，加性近似并不给出相对误差，更不给出精确系数——第 5.4 节将把这句话量化。

### 1.4 本课路线图

1. 第 2 节：把链环输入代数化为 braid word，区分 trace closure 与 plat closure 两种读出方式；
2. 第 3 节：Temperley--Lieb 代数与 Kauffman 的字典“交叉 $=$ 平滑的线性组合”，验证 $\rho_A$ 确实是 braid 群表示；
3. 第 4 节：在单位根上构造 path model，使表示变酉，并逐项解释 $\operatorname{poly}(m,n,k)$ 的电路复杂度；
4. 第 5 节：plat closure 算法（Hadamard test + 采样复杂度 + 误差尺度）；
5. 第 6 节：trace closure 算法（Markov trace、提纯、DQC1）；
6. 第 7 节：为什么这些近似问题对量子计算是完备的；
7. 第 8 节：一个从头算到尾的数值例子（$k=6$ 上的 Hopf 链环与三叶结）；
8. 第 9 节：推广到 HOMFLY 与 Khovanov 同调，以及 2025 年的 Hodge Laplacian 量子算法。

## 2. 把结代数化：braid 群与两种闭合

### 2.1 Braid 群

直观上，一个 **braid（辫）** 是 $n$ 股竖直的线：顶部有 $n$ 个端点、底部有 $n$ 个端点，每股从顶部某点沿竖直方向（允许左右绕行、永不回头）到达底部某点，两股交叉时记录谁在上。**Artin braid 群** $B_n$ 是这些辫在“端点固定、连续形变”意义下的等价类构成的群，乘法为竖直拼接（先做上段再做下段）。它由生成元 $\sigma_1,\dots,\sigma_{n-1}$ 给出，其中 $\sigma_i$ 表示第 $i$ 股与第 $i+1$ 股的一次**正交叉**（第 $i$ 股从上方跨过），$\sigma_i^{-1}$ 表示对应的负交叉。定义关系为：

$$
\sigma_i\sigma_j=\sigma_j\sigma_i\quad(|i-j|\ge2),\qquad
\sigma_i\sigma_{i+1}\sigma_i
=\sigma_{i+1}\sigma_i\sigma_{i+1}.
$$

第二条即著名的**辫关系 (braid relation)** $\sigma_i\sigma_{i+1}\sigma_i=\sigma_{i+1}\sigma_i\sigma_{i+1}$：两股在两处交叉后“谁在内谁在外”的两种顺序给出同一个辫。注意 $B_n$ 是无限群（$\sigma_i$ 的幂互不相同），而把每个 $\sigma_i$ 映为对换 $(i,i+1)$ 得到满同态 $B_n\to S_n$：辫比置换记录了更多信息——正是“交叉怎么绕”的那部分信息。

**指数和 (exponent sum)** 是 $B_n\to\mathbb Z$ 的同态：$w(b) = \sum_{j=1}^m \epsilon_j$，其中 $\epsilon_j\in\{\pm1\}$。第 1.2 节的 writhe 对“全部股向下定向”的辫图恰好等于 $w(b)$——这个量稍后将进入归一化因子。

(braid-closures)=
### 2.2 Alexander 定理与两种闭合

链环与辫由**闭合 (closure)** 操作连接起来。

> **定理 (Alexander, 1923)。** 任何有向链环都同痕于某个辫的**trace closure**。

**Trace closure（迹闭合）**：把 $n$ 股辫的第 $i$ 个顶端与第 $i$ 个底端用一条不交叉的弧连接（共 $n$ 条弧，全部绕在辫的外侧），得到一个闭链环。例如 2 股辫 $\sigma_1^m$ 的 trace closure 是 $(2,m)$ 型环面链环：$m=2$ 是 Hopf 链环、$m=3$ 是三叶结（第 8 节的例子正是它们）。

**Plat closure（plat 闭合）**：要求股数 $n$ 为偶数，把**相邻**端点成对封闭——顶部把 $1$ 接 $2$、$3$ 接 $4$、……，底部同样。这相当于在辫的上下各加一排“杯”与“帽”。并非每个链环都直接是某个辫的 plat closure，但任何链环都适当加厚后可用偶数股的 plat 表示；对本课的算法而言，输入就限定为“已经写成辫”的情形。

**为什么要区分两种闭合？** 因为它们对应两种**完全不同的读出方式**：

- **plat closure $\Rightarrow$ 矩阵元**。杯和帽选定了一对确定的初态/末态（后文的 $|\alpha\rangle$），链环的不变量正比于辫表示算子在该态上的矩阵元 $\langle\alpha|U_b|\alpha\rangle$。矩阵元用一次 Hadamard test 就能采样——这是 AJL 算法的读出，也是 BQP 完备性的载体。
- **trace closure $\Rightarrow$ 迹**。闭合把“第 $i$ 股接回第 $i$ 股”翻译成“对股指标求和”，对应表示算子的（加权）迹。归一化迹是 DQC1 模型的母语（第 6.3 节），这是 Shor--Jordan 结果的载体。

**输入表示与复杂度参数。** 本课的输入是长度 $m$ 的 braid word

$$
b=\sigma_{i_1}^{\epsilon_1}\sigma_{i_2}^{\epsilon_2}\cdots\sigma_{i_m}^{\epsilon_m},\qquad
1\le i_j\le n-1,\quad \epsilon_j\in\{\pm1\},
$$

连同股数 $n$ 与单位根参数 $k$（第 4 节）。输入大小为 $(m,n,k)$。对比第 1.3 节以交叉数 $c$ 计的结图：braid word 的长度 $m$ 正是闭合图的交叉数，所以“关于 $m$ 指数”的 skein 树与“关于 $c$ 指数”是同一件事。同章 [三维流形不变量](three-manifold-invariants.md) 一课对“输入表示决定复杂度”有同款讨论，可参照。

## 3. Temperley--Lieb 代数：从交叉到平滑

(tl-algebra-representation)=
### 3.1 图示演算

**Temperley--Lieb (TL) 代数** $\mathrm{TL}_n(d)$ 的元素是“没有交叉的配对图”的形式线性组合：图有 $n$ 个顶部端点与 $n$ 个底部端点，两两配对相连，连线互不交叉、不出边框。两个图的**乘法是竖直堆叠**：上图的底端接下图的顶端，然后压平。堆叠可能出现封闭的圈，规则是**每个圈抹去并乘上环值 $d$**。

对每个位置 $i\in\{1,\dots,n-1\}$ 定义生成元 $e_i$：把第 $i$ 与第 $i+1$ 个顶端用一条弧相连、第 $i$ 与第 $i+1$ 个底端用一条弧相连，其余股竖直穿过。直接数圈可以验证三条**定义性关系**：

$$
e_i^2=d\,e_i,\qquad
e_i e_{i\pm1}e_i=e_i,\qquad
e_i e_j=e_j e_i\ (|i-j|\ge2).
$$

逐条解释为什么成立：

- **$e_i^2 = d\,e_i$**：把两个 $e_i$ 堆叠，中间形成**一个**封闭小圈（内部那对弧上下相接围成），抹去后剩下的图恰好还是 $e_i$；所以 $e_i^2$ 等于“$e_i$ 乘上一个圈的值 $d$”。
- **$e_i e_{i+1} e_i = e_i$**：三层的堆叠中，外侧两股各绕一个“挂钩”后回到原位，中间没有封闭圈（$i$ 与 $i+2$ 位置的竖直股被 $e_{i+1}$ 的弧包住但不闭合），压平后恰是 $e_i$。这是三条中最需要画图核对的一条，留作练习 3 第 2 题让读者把连通分支数出来。
- **远交换律**：$e_i$ 与 $e_j$ 触及的端点集 $\{i,i+1\}$ 与 $\{j,j+1\}$ 不相交（$|i-j|\ge2$），堆叠次序显然无关。

这套演算与第 1.2 节的括号规则严丝合缝：**TL 的图就是括号展开后的“无交叉中间态”，环值 $d$ 就是脱圈规则里的 $-A^2-A^{-2}$。**

### 3.2 Braid 表示：把交叉展开成平滑

Kauffman 的关键观察：辫的每个交叉都可以就地展开成“平直型 + 转折型”两种平滑的线性组合，而平直型正是恒等图 $I$、转折型正是 $e_i$。于是定义**表示候选**

$$
\rho_A(\sigma_i) := A\,I + A^{-1}e_i .
$$

（约定提醒：哪种平滑配 $A$ 取决于正交叉的画法约定，另一约定恰好交换 $A$ 与 $A^{-1}$，对应镜像链环；本课固定此式。）由于 $e_i$ 只依赖 $i$ 附近两个位置，这个公式在任意 $n$ 下同时定义。因为 $A$ 是标量（中心元），多项式展开时可以随意合并同类项——后文的全部计算只用到这一点和三条 TL 关系。

**它真的是表示吗？** 这不是自动的：把群生成元的像随便写成代数元素，定义关系未必被保持。下一小节逐条检验，并发现一个漂亮的事实：**三条辫关系全部成立，当且仅当环值恰好是 $d = -A^2 - A^{-2}$**——与括号的拓扑要求一模一样。

### 3.3 表示定理

**Lemma 1（逆元）**. 对任意 $A$，$\rho_A(\sigma_i^{-1}) := A^{-1}I + A\,e_i$ 与 $\rho_A(\sigma_i)$ 互逆，当且仅当 $d = -(A^2+A^{-2})$。

**证明**。直接相乘（用 $e_i^2 = d\,e_i$）：

$$
\left(A I + A^{-1}e_i\right)\left(A^{-1}I + A e_i\right)
= I + A^2 e_i + A^{-2} e_i + e_i^2
= I + \left(A^2 + A^{-2} + d\right)e_i .
$$

右端等于 $I$ 当且仅当系数 $A^2+A^{-2}+d=0$。Q.E.D.

**Lemma 2（远交换律）**. $\rho_A(\sigma_i)\rho_A(\sigma_j)=\rho_A(\sigma_j)\rho_A(\sigma_i)$ 对 $|i-j|\ge2$ 成立，对任意 $d$。

**证明**。此时 $e_i e_j = e_j e_i$（TL 远交换律），而 $\rho_A(\sigma_i)$ 是 $I$ 与 $e_i$ 的线性组合，故两组乘法可交换。Q.E.D.

**Lemma 3（辫关系）**. $\rho_A(\sigma_i)\rho_A(\sigma_{i+1})\rho_A(\sigma_i) = \rho_A(\sigma_{i+1})\rho_A(\sigma_i)\rho_A(\sigma_{i+1})$ 成立，当且仅当 $d = -A^2-A^{-2}$。

**证明**。记 $u=e_i$、$v=e_{i+1}$。展开左边（$A$ 是标量，八项分别为从每个因子取 $I$ 或取生成元的所有组合；用 $u^2=du$、$uvu=u$）：

$$
\begin{aligned}
\left(A+A^{-1}u\right)\left(A+A^{-1}v\right)\left(A+A^{-1}u\right)
={}& A^3 + 2Au + Av + A^{-1}(uv+vu) + A^{-1}du + A^{-3}u \\
={}& A^3 + \left(2A + A^{-1}d + A^{-3}\right)u + Av + A^{-1}(uv+vu).
\end{aligned}
$$

（逐项来源：$A\!\cdot\!A\!\cdot\!A = A^3$；两次“$I\,I\,u$”各贡献 $Au$；“$I\,v\,I$”贡献 $Av$；“$I\,v\,u$”与“$u\,v\,I$”各贡献 $A^{-1}$ 倍的 $vu,uv$；“$u\,I\,u$”贡献 $A^{-1}u^2 = A^{-1}du$；“$u\,v\,u$”贡献 $A^{-3}uvu = A^{-3}u$，最后一步用了 $e_ie_{i+1}e_i = e_i$。）右边由对称性（$u\leftrightarrow v$）为

$$
A^3 + Au + \left(2A + A^{-1}d + A^{-3}\right)v + A^{-1}(uv+vu).
$$

两式相减：

$$
\text{左边}-\text{右边} = \left(A + A^{-1}d + A^{-3}\right)(u - v).
$$

由于 $u - v \ne 0$（两个不同的图），辫关系成立当且仅当 $A + A^{-1}d + A^{-3} = 0$，两边乘 $A$ 即 $A^2 + d + A^{-2} = 0$。Q.E.D.

把三个引理合起来：

**Theorem 4（Kauffman）**. 取环值 $d = -A^2 - A^{-2}$ 时，$\rho_A: B_n \to \mathrm{TL}_n(d)$ 是群同态（把 $\sigma_i^{\pm1}$ 映为上述可逆元素）；并且此时括号在 R2 移动下的不变性（Lemma 1 的恒等式）与 R3 移动下的不变性（Lemma 3 的恒等式）逐条成立，R1 的亏损恰好是 $(-A)^{\pm3}$ 因子，被 $(-A)^{-3w}$ 补偿。

同一个条件 $A^2+A^{-2}+d = 0$ 出现了两次：一次保证**代数**（这是表示），一次保证**拓扑**（括号在 R2 下不变）。第 4.1 节将看到它第三次出现——保证**量子**（表示可取为酉）。这不是巧合：环值 $d$ 同时是“圈抹去后的代数权重”、“拓扑自洽的参数”、“酉性的参数”这三个角色的唯一交点。

**闭合后的读出**。对 trace closure，把 TL 元素 $x=\sum_j c_j x_j$（$x_j$ 为配对图）闭合：每个图 $x_j$ 闭合后是若干不相交圆圈之并，其括号是 $d$ 的幂。由线性性，

$$
\langle \widehat{b}\rangle = \text{（把 }\rho_A(b)\text{ 中每个图闭合、数圈、加权求和）}，
$$

其中 $\widehat b$ 表示 $b$ 的 trace closure。第 8 节的例子将把这条“数圈”规则一步步算出来。

## 4. 单位根与 path model：让表示变酉

(unitary-path-model)=
### 4.1 酉性引理

量子线路只能实现酉算子，而 $\rho_A(\sigma_i) = A I + A^{-1}e_i$ 一般既不酉也不可逆（可逆性已被 Theorem 4 安排好）。现在把 $e_i$ 实现为一个 Hilbert 空间上的算子，并问：何时 $\rho_A(\sigma_i)$ 酉？

**Lemma 5（酉性）**. 设 $e$ 是 Hilbert 空间上的自伴算子（$e^\dagger = e$）且满足 $e^2 = d\,e$，$d\in\mathbb R$。取 $|A|=1$。则

$$
U := A\,I + A^{-1}e
$$

是酉算子，当且仅当 $d = -(A^2 + A^{-2})$。

**证明**。由 $|A| = 1$ 有 $\bar A = A^{-1}$，故 $U^\dagger = \bar A I + \bar A^{-1} e^\dagger = A^{-1}I + A\,e$。于是（用自伴性与 $e^2 = de$）

$$
U U^\dagger = \left(AI + A^{-1}e\right)\left(A^{-1}I + Ae\right)
= I + \left(A^2 + A^{-2} + d\right)e .
$$

若 $A^2+A^{-2}+d = 0$，则 $UU^\dagger = I$，且同理 $U^\dagger U = I$，$U$ 酉。反之，若 $U$ 酉则 $UU^\dagger = I$，即 $(A^2+A^{-2}+d)\,e = 0$；取 $e \ne 0$ 的表示（后文的 path model 即是）即得 $A^2+A^{-2}+d=0$。Q.E.D.

于是策略清楚了：**在单位根上取 $A$，使 $d = -A^2-A^{-2}$ 为实数**，并把 $e_i$ 实现为自伴算子。具体地，固定整数 $k\ge3$（后文称 level），取

$$
t = e^{2\pi i/k},\qquad A = t^{-1/4},\qquad\text{于是}\quad
A^2 = e^{-\pi i/k},\qquad d = -\left(A^2+A^{-2}\right) = -2\cos(\pi/k)\in\mathbb R .
$$

（$A$ 是 $4k$ 次单位根；分支选取的差别只影响整体相位与手性约定。）此时 $|d| = 2\cos(\pi/k)$。注意一个即将变得关键的数值事实：

$$
|d| = 2\cos(\pi/k) = \text{路径图 } A_{k-1} \text{ 的谱半径（下一小节验证）}.
$$

### 4.2 $A_{k-1}$ 图与 Perron--Frobenius 权重

取 $k-1$ 个顶点排成一条线、相邻相连的**路径图 $A_{k-1}$**（Dynkin 记号），顶点标号为 $1,\dots,k-1$。它的邻接矩阵最大特征值（谱半径）是 $2\cos(\pi/k)$，对应的正特征向量分量为

$$
\lambda_j = \sin\!\left(\frac{\pi j}{k}\right),\qquad j = 1,\dots,k-1 .
$$

这两句话可以直接验证：顶点 $j$ 的两个邻居是 $j\pm1$（端点 $1$ 与 $k-1$ 各只有一个邻居，下式同样成立），于是特征向量方程就是**和差化积恒等式**

$$
\sin\!\frac{\pi(j-1)}{k} + \sin\!\frac{\pi(j+1)}{k}
= 2\sin\!\frac{\pi j}{k}\cos\!\frac{\pi}{k},\qquad j=2,\dots,k-2,
$$

即向量 $(\lambda_j)$ 被邻接矩阵乘后整体放大 $2\cos(\pi/k)$ 倍。两个端点只有一个邻居，方程退化为 $\lambda_2 = 2\cos(\pi/k)\,\lambda_1$，即 $\sin(2\pi/k) = 2\sin(\pi/k)\cos(\pi/k)$——二倍角公式，同样成立（顶点 $k-1$ 处由 $\sin(\pi - x) = \sin x$ 化归为同一等式）。由 Perron--Frobenius 定理，正特征向量属于谱半径，故谱半径确为 $2\cos(\pi/k)$。$k=6$ 时 $\lambda = (\tfrac12, \tfrac{\sqrt3}{2}, 1, \tfrac{\sqrt3}{2}, \tfrac12)$、谱半径 $\sqrt3$，与 $|d|=\sqrt3$ 一致。

$\lambda_j$ 就是原文文献中的 **Perron--Frobenius 权重**，它将出现在两个地方：构造使 $e_i$ 自伴的内积（本节），以及 Markov trace 的终点权重（第 6 节）。

### 4.3 Path model：路径基与量子比特编码

**Hilbert 空间。** path model 的态空间由**路径**标记：路径是图 $A_{k-1}$ 上长度为 $n$ 的顶点序列

$$
p = (p_0, p_1, \dots, p_n),\qquad p_0 = 1,\qquad |p_{j+1}-p_j| = 1,\qquad 1\le p_j\le k-1,
$$

即从顶点 $1$ 出发、每步向相邻顶点移动、永不越界的行走。全体这样的路径张成一个有限维复向量空间，取路径为基（内积由 $\lambda$ 权重按文献标准方式修正后使 $e_i$ 自伴——修正的具体形状不影响本课后续内容，我们只用到“$e_i$ 自伴、满足 TL 关系”这一事实，其存在性的构造性证明见 AJL 文）。

**量子比特编码。** 每一步只有“向上 ($p_{j+1} = p_j+1$)”与“向下 ($p_{j+1} = p_j-1$)”两种选择，正好编码为一个量子比特；$n$ 步用 $n$ 个量子比特。全体 $2^n$ 个比特串中，越界（触到 $0$ 或 $k$）的是**非法路径**，被排除在合法子空间之外；由于每一步的合法性只依赖“当前高度”，合法子空间可以用逐位的受控约束标记。对固定 $k$，合法路径数目按 $(2\cos(\pi/k))^n$ 量级增长（受谱半径控制，这是随机游走的标准渐近），严格小于 $2^n$ 但对变化 $n$ 仍是指数——这正是“经典上指数大、量子上 $n$ 个比特就装得下”的典型处境。

**生成元的作用。** $e_i$ 只触及路径的第 $i$ 与 $i+1$ 步附近的局部形状：若这两步构成“先上后下”或“先下后上”的转折，$e_i$ 把转折改写（翻转或加权保留），矩阵元由 Perron--Frobenius 权重的**比值** $\lambda_a/\lambda_b$ 给出；若两步同向（单调穿过），$e_i$ 的作用为零。这一局部性的代数后果是：TL 的三条关系（第 3.1 节）逐条成立——它们的验证就是把比值化简，背后正是上节的和差化积恒等式。对本课而言，关键结论是：

> 在单位根 $A$（$d = -A^2-A^{-2}$）处，配以 $\lambda$ 权重内积，每个 $\rho_A(\sigma_i)$ 是作用在**常数个相邻步寄存器**上的酉算子。

（这是原文文献的表述：适当单位根上，path-model 内积使这些算子酉。第 4.1 节的 Lemma 5 说明了“为什么恰好在这个参数上”。）

**Plat 态。** plat closure 的杯—帽结构对应一个特殊初态 $|\alpha\rangle$：其支集集中在“路径在相邻高度间规则往返”的路径上（每个杯位强迫一次上—下往返）。这样的态由位置的奇偶性确定，是浅层电路可制备的乘积型态。

### 4.4 电路复杂度：逐项清单

把 braid word $b = \sigma_{i_1}^{\epsilon_1}\cdots\sigma_{i_m}^{\epsilon_m}$ 编译成量子电路 $U_b := \rho_A(b)$，按从右到左逐个执行 $\rho_A(\sigma_{i_j})^{\epsilon_j}$。总规模 $\operatorname{poly}(m,n,k)$ 的每个因子各有着落：

- **$m$（交叉数）**：每个字母是**一个**局部酉门，门数关于 $m$ 线性。这是 AJL 算法的复杂度陈述：运行时间关于 $m,n,k$ 多项式。
- **$n$（股数）**：门 $\rho_A(\sigma_i)$ 作用在第 $i,i+1$ 步寄存器（各 $\lceil\log k\rceil$ 或常数个比特，视编码而定），但“第 $i$ 个”需要寻址：用交换网络把目标寄存器移到一起、作用、再移回，每次门的布线代价 $O(n)$（或用寻址门 $O(\log n)$），总计 $O(mn)$ 量级。此外总寄存器数为 $n$ 个步比特。
- **$k$（level）**：门的矩阵元是 $\lambda_a/\lambda_b$ 型比值与 $A$ 的幂，都是可经典预计算的 $O(k)$ 个常数（实现时取足够精度的定点近似）；合法性判定需要知道“高度是否在 $1..k-1$ 内”，涉及 $\log k$ 个比特。
- **辅助**：Hadamard test 需要额外 $1$ 个比特（第 5.2 节）。

所以：**电路大小 $\operatorname{poly}(m,n,k)$、量子比特数 $n + O(\log k) + O(1)$**。注意 $k$ 既可作为输入（算法对 $k$ 多项式），也可固定为常数（第 7 节的完备性恰恰取固定的 $k$）。

## 5. Plat closure：估计一个矩阵元

### 5.1 公式的形状

对偶数股的 braid word $b$，其 plat closure 的 Jones 值在单位根 $t = e^{2\pi i/k}$ 处可以写成

$$
J_{\operatorname{plat}(b)}\!\left(e^{2\pi i/k}\right) = C(b,k)\,\langle\alpha|U_b|\alpha\rangle ,
$$

其中三个符号的含义：

- $U_b = \rho_A(b)$ 是第 4 节编译出的电路；
- $|\alpha\rangle$ 是 cup-cap 初态（第 4.3 节）；
- $C(b,k)$ 是**已知的、经典多项式时间可计算**的归一化因子，它收集三类修正：辫的指数和（writhe）带来的 framing 因子 $(-A)^{-3w(b)}$（plat 闭合时还包含股方向反转引起的符号修正，AJL 文中有显式公式）、闭合产生的圈数对应的 $d$ 的幂、以及态 $|\alpha\rangle$ 的归一化。

这句话的算法含义是：**量子部分只需要输出一个复数 $\langle\alpha|U_b|\alpha\rangle$ 的近似；所有拓扑换算都在经典侧完成。**剩下的任务是把“估计矩阵元”做快、做准。

(hadamard-test-additive-approximation)=
### 5.2 Hadamard test 的完整推导

记 $a := \langle\alpha|U_b|\alpha\rangle$（$|a|\le1$，因为它是酉算子单位矢间的内积——Cauchy--Schwarz）。**Hadamard test** 用一个辅助比特（ancilla）与受控-$U_b$ 把 $a$ 的实部与虚部变成辅助比特的测量概率。推导如下。

第一步，制备辅助比特 $\frac{1}{\sqrt2}(|0\rangle+|1\rangle)$（一个 Hadamard 门作用于 $|0\rangle$ 即得），目标寄存器制备 $|\alpha\rangle$，联合态为

$$
|\Psi_1\rangle = \frac{1}{\sqrt2}\left(|0\rangle + |1\rangle\right)|\alpha\rangle .
$$

第二步，执行受控-$U_b$（辅助比特为 $|1\rangle$ 时作用 $U_b$）：

$$
|\Psi_2\rangle = \frac{1}{\sqrt2}\left(|0\rangle|\alpha\rangle + |1\rangle U_b|\alpha\rangle\right).
$$

第三步，对辅助比特测量可观测量 $X$。注意 $X$ 的本征态正是 $|+\rangle,|-\rangle$，而

$$
\langle\Psi_2|X\otimes I|\Psi_2\rangle
= \frac12\left(\langle\alpha|\langle0| + \langle\alpha|U_b^\dagger\langle1|\right)\left(|1\rangle|\alpha\rangle\cdot 1 + |0\rangle U_b|\alpha\rangle\cdot 1\right)
$$

（这里用了 $X|0\rangle = |1\rangle$、$X|1\rangle = |0\rangle$；展开出的四项中，辅助比特指标相同的两项因 $\langle0|0\rangle=\langle1|1\rangle=1$ 保留，指标不同的两项因 $\langle0|1\rangle=\langle1|0\rangle=0$ 消去。）保留的两项是

$$
= \frac12\left(\langle\alpha|U_b|\alpha\rangle + \langle\alpha|U_b^\dagger|\alpha\rangle\right)
= \frac12\left(a + \bar a\right) = \operatorname{Re} a .
$$

即**辅助比特的 $X$ 期望恰是 $\operatorname{Re} a$**，从而测得 $|+\rangle$ 的概率为 $p_+ = \frac{1+\operatorname{Re}a}{2}$。

第四步，测虚部：对辅助比特测量 $Y$。用 $Y|0\rangle = i|1\rangle$、$Y|1\rangle = -i|0\rangle$（即 $\langle0|Y|1\rangle = -i$、$\langle1|Y|0\rangle = i$）：

$$
\langle\Psi_2|Y\otimes I|\Psi_2\rangle
= \frac12\left((-i)\,\langle\alpha|U_b|\alpha\rangle + (i)\,\langle\alpha|U_b^\dagger|\alpha\rangle\right)
= \frac{i}{2}\left(\bar a - a\right) = \operatorname{Im} a .
$$

（末步用了 $\bar a - a = -2i\,\operatorname{Im}a$。）实践上 $Y$ 基测量等价于在受控门后给辅助比特加一个相位门再做 $X$ 基测量。于是

$$
\operatorname{Re}a = 2p_+ - 1,\qquad \operatorname{Im}a = \langle Y\rangle ,
$$

两个概率各用一组重复测量即可还原复数 $a$。

### 5.3 采样复杂度：Hoeffding 与振幅估计

单次 Hadamard test 给出一个 Bernoulli 随机变量（参数 $p_+\in[0,1]$）。用 $K$ 次独立重复的经验频率 $\hat p$ 估计 $p_+$，**Hoeffding 不等式**给出

$$
\Pr\!\left[\,|\hat p - p_+| \ge \delta\,\right] \le 2e^{-2K\delta^2},
$$

要常数置信度（如 $\le 0.05$）需 $2e^{-2K\delta^2}\le 0.05$，即 $K \ge \frac{\ln 40}{2\delta^2}$，也就是 $K = \Theta(1/\delta^2)$。取 $\delta = \epsilon/2$（这样 $|2\hat p - 1 - \operatorname{Re}a| \le 2\delta = \epsilon$），得实部到加性 $\epsilon$ 需要

$$
K = \Theta\!\left(\frac{1}{\epsilon^2}\right)
$$

次电路运行；虚部同阶。每次运行执行一遍 $U_b$ 电路（代价 $\operatorname{poly}(m,n,k)$），所以总复杂度

$$
T_{\text{sampling}} = \frac{\operatorname{poly}(m,n,k)}{\epsilon^2}.
$$

**振幅估计 (amplitude estimation)** 把精度因子开根号：$O(1/\epsilon)$ 次**相干**调用给出同样加性精度（第 3 章已证；其机制是把“成功概率 $\mu$”编成 Grover 型迭代的旋转角 $2\omega$，$\sin^2\omega = \mu$，再用相位估计读角）。代价有二：需要实现受控-$U_b$ 的幂 $U_b^{2^j}$（把电路重复 $2^j$ 次，几何级数求和后总门数仍是 $\operatorname{poly}(m,n,k)\cdot O(1/\epsilon)$）；且不含测量地相干复用中间态。于是

$$
T_{\text{AE}} = \frac{\operatorname{poly}(m,n,k)}{\epsilon}.
$$

两种读出的取舍就是“$1/\epsilon^2$ 次含测量运行”与“$1/\epsilon$ 次相干运行”之间的取舍；对 $\epsilon = 1/\operatorname{poly}$ 两者都是多项式，对指数小的 $\epsilon$ 两者都指数——**精度的多项式性是硬边界**。

### 5.4 误差尺度：加性近似买到了什么

把矩阵元的估计 $\hat a$（$|\hat a - a|\le\epsilon$）代回第 5.1 节的公式，Jones 值的误差是

$$
\left|\,J_{\operatorname{plat}(b)} - C(b,k)\,\hat a\,\right| \le |C(b,k)|\,\epsilon .
$$

这个不等式是本课所有“保留条款”的技术根源，值得把每一层说透：

- **$|C(b,k)|$ 可以关于 $m$ 指数大。**它包含 $d$ 的幂（每多一个闭合圈贡献一个 $d$，$d$ 的模是常数但幂次随 $n,m$ 增长）与 framing 因子。于是“矩阵元的 $\epsilon$ 加性近似”换算到 Jones 值是“尺度 $|C|$ 上的加性近似”——若 $|C|$ 指数大，绝对误差 $\epsilon|C|$ 对典型的 Jones 值可能毫无信息量。
- **它不是相对误差。**相对误差要求 $|\hat J - J| \le \epsilon|J|$；对 $|J|\ll|C|$ 的链环，由 $|J| = |C||a|$ 可知这要求 $\epsilon \lesssim |a|$，而典型矩阵元振幅约 $1/\sqrt{\text{路径空间维数}}$、随 $n$ 指数小——相对逼近一般需要指数采样。
- **它更不是精确系数。**Jones 是 Laurent 多项式，精确读出某个系数需要把误差压到多项式间距以内；一般求值点上这保持 $\#\mathsf{P}$-hard（第 1.3 节）。

一句话总结：**量子算法给出的是“相对自然归一化 $C$ 的加性近似”，这是一个明确定义、有内容、但范围有限的承诺。**夸大它（说成“量子计算机算出了 Jones 多项式”）与贬低它（说成“毫无意义”）都不对——第 7 节将看到，恰恰是这个受限的近似问题，对量子计算本身是完备的。

## 6. Trace closure：Markov trace 与 DQC1

### 6.1 为什么 trace closure 需要加权迹

回忆 Markov 定理：两个辫 $b\in B_n$、$b'\in B_{n'}$ 的 trace closure 同痕，当且仅当它们可通过两类移动互变：**共轭**（$b\mapsto xbx^{-1}$，同群内）与**稳定化**（$b\mapsto b\,\sigma_n^{\pm1}\in B_{n+1}$，加一股打一次交叉）。要在表示论一侧得到链环的泛函，必须找到一个对这两类移动不变（差已知因子）的线性泛函：

- 共轭不变 $\Rightarrow$ 它必须是**迹**（trace 性质 $\operatorname{tr}(xy) = \operatorname{tr}(yx)$）；
- 稳定化不变 $\Rightarrow$ 它在“多闭合一股”时的行为被固定，这**唯一确定**了各股指标上的权重——计算的结果正是 Perron--Frobenius 权重。

在 path model 的路径基上，这个 **Markov trace** 写成对路径终点的加权归一化迹：

$$
\operatorname{Tr}_{\rm Markov}(U_b) = \sum_{p}\,\pi(p)\,\langle p|U_b|p\rangle,\qquad
\pi(p) \propto \lambda_{p_n},
$$

求和跑遍合法路径 $p$，权重 $\pi(p)$ 只依赖终点 $p_n$ 所在顶点（$\lambda_{p_n} = \sin(\pi p_n/k)$），归一化成概率分布。Jones 值等于这个迹乘上一个已知的经典归一化（包含 writhe 因子与 $d$ 的幂）。直觉：trace closure 把“第 $i$ 股接回第 $i$ 股”翻译成“对股指标求和”，而路径的终点记录的正是“这 $n$ 股组合成的拓扑荷落在哪个 sector”——加权求和就是按 sector 配平。

(markov-trace-dqc1)=
### 6.2 两条实现路线与一个参数平衡

**路线一：提纯 (purification)。**$\pi(p)$ 只依赖终点寄存器，故加权叠加态

$$
|\sqrt{\pi}\rangle := \sum_p \sqrt{\pi(p)}\,|p\rangle
$$

是一个**可高效制备**的态：权重只依赖终点，故 $\pi$ 是一个经典高效可采样的分布——先按 $\lambda_v\cdot N_v$（$N_v$ 为终点在 $v$ 的合法路径数，可动态规划经典计算）抽终点 $v$、再均匀抽一条到 $v$ 的路径——相干版沿同一结构制备即可。在它上面做一次 Hadamard test（第 5.2 节，把 $|\alpha\rangle$ 换成 $|\sqrt\pi\rangle$），期望值就是

$$
\langle\sqrt{\pi}|\,U_b\,|\sqrt{\pi}\rangle
= \sum_{p,q}\sqrt{\pi(p)\pi(q)}\,\langle q|U_b|p\rangle\cdot\langle p|q\rangle
= \sum_p \pi(p)\,\langle p|U_b|p\rangle
= \operatorname{Tr}_{\rm Markov}(U_b),
$$

中间一步用了路径基的正交归一性 $\langle p|q\rangle = \delta_{pq}$。于是**一次 Hadamard test 直接采样 Markov trace 本身**，第 5.3 节的采样复杂度原样适用：$\operatorname{poly}(m,n,k)/\epsilon^2$，或振幅估计的 $/\epsilon$。

**路线二：经典抽样 + 逐个 Hadamard test。**也可以先用经典随机数按 $\pi$ 抽路径 $p$，再对每个 $|p\rangle$ 做 Hadamard test 估计 $\langle p|U_b|p\rangle$，最后平均。这不需要制备 $|\sqrt\pi\rangle$，代价是误差来源变成两个。

**两阶段误差的平衡（展示求解过程）。**设抽出 $s$ 个路径、每个做 $K$ 次 Hadamard 测量。估计量的误差有两个独立来源：(i) 对 $p$ 的 Monte-Carlo 抽样，贡献标准差 $\sigma_\pi/\sqrt s$，其中 $\sigma_\pi^2 := \operatorname{Var}_{p\sim\pi}[\operatorname{Re}\langle p|U_b|p\rangle]$ 是各 sector 对角元在 $\pi$ 下的方差；(ii) 每个路径的 Bernoulli 测量噪声，贡献 $c/\sqrt K$（$c$ 为常数，由第 5.3 节 Hoeffding 的换算决定）。总误差近似为两者平方和的平方根，为简单起见按最坏情形相加：

$$
\operatorname{err} \approx \frac{\sigma_\pi}{\sqrt s} + \frac{c}{\sqrt K},\qquad \text{预算约束 } sK = N\ (\text{总电路运行数}).
$$

把 $K = N/s$ 代入，得 $f(s) = \sigma_\pi s^{-1/2} + c\,(s/N)^{1/2}$。对 $s$ 求导置零：

$$
f'(s) = -\frac{\sigma_\pi}{2}s^{-3/2} + \frac{c}{2\sqrt N}\,s^{-1/2} = 0
\;\Longrightarrow\;
\frac{c}{2\sqrt N}s^{1/2} = \frac{\sigma_\pi}{2}s^{-1/2}
\;\Longrightarrow\;
s^{*} = \frac{\sigma_\pi\sqrt N}{c},\qquad K^{*} = \frac{N}{s^*} = \frac{c\sqrt N}{\sigma_\pi}.
$$

代回得 $f(s^*) = 2\sqrt{\sigma_\pi c}\;/\;N^{1/4}$，即最优总误差 $\Theta(N^{-1/4})$，且最优分配让**两项误差同阶**（各占一半）——这就是“取参数使两项同阶”的平衡原则的一个具体实例：样本该在“多抽几个路径”与“每个路径测准一点”之间按 $\sigma_\pi : c$ 分配。若 $\sigma_\pi$ 很小（各 sector 对角元几乎相同），就少抽路径、每个多测；反之亦然。注意两个阶段只能换来 $N^{-1/4}$：预算被劈成两半，每个阶段只分到 $\sqrt N$ 次资源、各贡献 $N^{-1/8}$ 的误差。对比之下，**路线一（提纯）把两个误差源合并成一个**——经典混合的方差被相干地吸收进 $|\sqrt\pi\rangle$，只剩量子测量噪声一项，误差回到 $N^{-1/2}$（即 $1/\epsilon^2$ 采样）。这就是提纯优于两阶段抽样的定量理由。

### 6.3 DQC1：归一化迹的母语

**DQC1（deterministic quantum computation with one clean qubit，单干净比特量子计算）**是 Knill 与 Laflamme 于 1998 年提出的计算模型：$n$ 个**完全混合**的量子比特加**一个**干净比特，允许对全体做任意酉操作后测量干净比特。它介于经典与 BQP 之间（$\mathsf{DQC1}\subseteq\mathsf{BQP}$，一般认为严格包含于 BQP），最著名的展示是它能在多项式时间内估计任意酉算子的归一化迹 $\frac{1}{2^n}\operatorname{Tr}U$——推导只需三行。

初始态（干净比特 $|0\rangle$，其余最大混合）：

$$
\rho_0 = |0\rangle\langle 0| \otimes \frac{I}{2^n}.
$$

对干净比特做 $H$，再执行受控-$U$，然后只看干净比特的约化态。$H$ 之后 $\rho = \frac12\left(|0\rangle\langle0| + |0\rangle\langle1| + |1\rangle\langle0| + |1\rangle\langle1|\right)\otimes\frac{I}{2^n}$。受控-$U = |0\rangle\langle0|\otimes I + |1\rangle\langle1|\otimes U$ 的共轭作用逐块计算：对角块 $|0\rangle\langle0|\otimes I$ 与 $|1\rangle\langle1|\otimes I$ 分别映到 $|0\rangle\langle0|\otimes I$ 与 $|1\rangle\langle1|\otimes UU^\dagger = |1\rangle\langle1|\otimes I$（$U$ 酉）；非对角块 $|0\rangle\langle1|\otimes M \mapsto |0\rangle\langle1|\otimes MU^\dagger$、$|1\rangle\langle0|\otimes M\mapsto |1\rangle\langle0|\otimes UM$。于是

$$
\rho' = \frac{1}{2^{n+1}}\left(|0\rangle\langle0|\otimes I + |1\rangle\langle1|\otimes I + |0\rangle\langle1|\otimes U^\dagger + |1\rangle\langle0|\otimes U\right).
$$

对混合寄存器求迹（$\operatorname{Tr}I = 2^n$，$\operatorname{Tr}U = \operatorname{Tr}U$），记 $\tau := \operatorname{Tr}(U)/2^n$：

$$
\rho'_{\rm clean} = \frac12\begin{pmatrix}1 & \bar\tau\\ \tau & 1\end{pmatrix},
\qquad
\langle X\rangle = \operatorname{Re}\tau,\qquad \langle Y\rangle = \operatorname{Im}\tau .
$$

（最后两个等号：$\operatorname{Tr}(\rho'_{\rm clean}X) = \frac12(\tau + \bar\tau)$ 等。）**整个过程没有制备任何纯的 $n$ 比特态**——归一化迹本来就是混合态可观测量。

这正是 Markov trace 的形状：一个“对角矩阵元的加权平均”。Shor 与 Jordan 由此证明，**某些** Jones trace closure 近似（在论文指定的单位根、closure 与加性误差尺度下）是 **DQC1-complete** 的：它既能在 DQC1 中完成（上述电路加上对路径 sector 的经典随机化，把权重 $\pi$ 并入抽步骤），又足以模拟 DQC1 中的任意计算。注意保留条款：是“某些”——完备性结论绑定于特定的根与误差归一化，不是说所有 Jones 迹都同样难；也不是说 DQC1 能做 plat closure 的完备版本（那属于 BQP，第 7 节）。

## 7. 为什么 BQP-hard：拓扑量子计算视角

第 4、5 节给出了“plat closure 的加性近似 $\in$ BQP”。反方向更强：**同一个近似问题对 BQP 是完备的**。证明思路来自拓扑量子计算，两个要件：

**要件一：编织就是计算（表示的稠密性）。**在 $(2+1)$ 维 TQFT 描述的任意子系统中，$n$ 个任意子的编织（braid）作用于系统的融合空间，给出正是 braid 群的（射影）酉表示——与本课的 $\rho_A$ 同族。对合适的 level（例如 $k=5$，对应 Fibonacci 型任意子理论），该表示的像在相应的酉群中**稠密**：任意目标酉门都能被某个编织词逼近。这是 Freedman--Larsen--Wang 一线的稠密性定理；配合 Solovay--Kitaev 型编译（把“稠密”升级为“多项式长度词逼近到 $1/\operatorname{poly}$ 精度”），得到：**任何量子电路都可以被经典多项式时间编译成一个多项式长度的 braid word $b_C$。**（AJL 文的表述即：其算法在五次单位根 $e^{2\pi i/5}$ 处解决的是 BQP-complete 问题，依据正是 Freedman 等人的结果。）

**要件二：电路的接受振幅被编码为辫的矩阵元。**编译可以安排得使任意电路 $C$ 的接受振幅（或接受概率）与 $b_C$ 的表示矩阵元相差一个**已知的**归一化因子：

$$
\langle 0|C|0\rangle \;\approx\; \langle\alpha|\rho(b_C)|\alpha\rangle \times (\text{已知尺度}).
$$

直觉：$|\alpha\rangle$ 扮演电路的 $|0\dots0\rangle$ 初态，编织 $b_C$ 扮演电路演化，读出矩阵元扮演测量振幅——拓扑系统“物理上就是”一台量子计算机，其振幅天然是拓扑不变量的值。

**拼起来的归约。**假设存在（经典或量子）算法 $\mathcal A$ 能在 AJL 指定的归一化尺度内加性逼近 $\langle\alpha|\rho(b_C)|\alpha\rangle$。给定任意 BQP 电路 $C$：经典多项式时间编译出 $b_C$，运行 $\mathcal A$，乘上已知尺度读出 $\langle0|C|0\rangle$ 的近似——精度取到足以区分“接受概率 $\ge 2/3$”与“$\le 1/3$”即可（中间留有常数间隙，编译误差可以做得远小于间隙）。于是 $\mathcal A$ 解决任意 BQP 问题，即该近似问题 BQP-hard；结合第 5 节的算法，它是 **BQP-complete**。

**保留条款（务必逐条记牢）。**被证明完备的是以下三者**同时成立**的问题版本：

1. **特定单位根**：$k$ 取使表示稠密的那一档（如 $k=5$），不是“对所有根”；
2. **特定 closure**：plat closure 的矩阵元形式（trace closure 对应 DQC1 侧）；
3. **特定加性误差尺度**：误差相对于指定的（可指数大的）归一化 $C(b,k)$ 声明，这是问题定义的一部分，不是算法偷懒。

因此该结论**不表示**“Jones 多项式被量子计算机攻克了”：精确值与相对误差在第 5.4 节的意义下仍然困难（一般点 $\#\mathsf{P}$-hard），也不表示所有求值点同等困难（特殊点有多项式经典算法，第 1.3 节）。同章 [三维流形不变量](three-manifold-invariants.md) 一课对 Turaev--Viro 不变量的 BQP-complete 结论有平行的讨论，可对照阅读。

(worked-example-k6)=
## 8. 手算例子：$k=6$ 上的 Hopf 链环与三叶结

本节把前文的机制在一个能完全手算的设定里走一遍：两股辫、$k=6$。**所有代数只用三条 TL 关系与“数圈”规则**，量子算法逼近的正是我们一步步算出的这些数。

**设定。**取 $k = 6$，故 $t = e^{2\pi i/6} = e^{i\pi/3}$，$A = t^{-1/4} = e^{-i\pi/12}$（则 $A^2 = e^{-i\pi/6}$）。环值

$$
d = -\left(A^2 + A^{-2}\right) = -\left(e^{-i\pi/6}+e^{i\pi/6}\right) = -2\cos\frac{\pi}{6} = -\sqrt3 .
$$

注意 $|d| = \sqrt3 = 2\cos(\pi/6)$ 恰是 $A_5$ 的谱半径（第 4.2 节），且 $\lambda_1 = \sin(\pi/6) = \tfrac12$、$\lambda_3 = \sin(\pi/2) = 1$。两股（$n=2$）的合法路径只有

$$
p = (1,2,1)\quad\text{与}\quad p = (1,2,3),
$$

所以 path model 的态空间是**二维**的——本例中量子电路 $U_b$ 就是一个 $2\times2$ 酉矩阵（作用在这两个基矢张成的空间上）。

**第一步：验证酉性条件。**$A^2 + A^{-2} = \sqrt3 = -d$，故 Lemma 5 的条件 $A^2+A^{-2}+d = 0$ 成立，$\rho_A(\sigma_1) = A\,I + A^{-1}e_1$ 酉；Theorem 4 同时保证它是 $B_2$ 的表示（$B_2$ 只有一个生成元，辫关系自动成立，但引理 1 的可逆性条件已核对）。把 $A + A^{-1}d$ 这个关键数值实际算出来，看它确实落在单位圆上（提出公因子 $e^{-i\pi/12}$，再用 $\sqrt3\,e^{i\pi/6} = \tfrac32 + \tfrac{\sqrt3}{2}i$ 与 $1 - \tfrac32 - \tfrac{\sqrt3}{2}i = -\tfrac12 - \tfrac{\sqrt3}{2}i = e^{-i\,2\pi/3}$）：

$$
A + A^{-1}d = e^{-i\pi/12}\left(1 - \sqrt3\,e^{i\pi/6}\right)
= e^{-i\pi/12}\cdot e^{-i\,2\pi/3}
= e^{-i\,3\pi/4},\qquad |A + A^{-1}d| = 1 .
$$

而 $A$ 本身模长为 $1$：$\rho_A(\sigma_1)$ 的两个“候选本征方向”（$e_1$ 取本征值 $0$ 或 $d$）上的本征值 $A$ 与 $A+A^{-1}d$ 都在单位圆上——这正是 Lemma 5 在本例中的数值体现。

**第二步：单个卷（校准坐标）。**$\rho_A(\sigma_1) = A\,I + A^{-1}e_1$。把两项分别 trace-close：恒等图（两条竖线）闭合后是**两个**不相交圆圈（每条竖线与自己的闭合弧成一圈），括号 $d$；$e_1$（上弧接上弧、下弧接下弧）闭合后是**一个**圆圈，括号 $1$。所以

$$
\langle\widehat{\sigma_1}\rangle = A\cdot d + A^{-1}\cdot 1 = \left(-A^3 - A^{-1}\right) + A^{-1} = -A^3 .
$$

这正是第 1.2 节预言的单卷行为（$\langle\text{卷}\rangle = -A^{\pm3}$），与“补偿因子 $(-A)^{-3w}$”的机制吻合：带因子后 $(-A)^{-3}\cdot(-A^3) = 1$，而 $\widehat{\sigma_1}$ 是平凡结，$V = 1$。**校准通过。**

**第三步：Hopf 链环（$b=\sigma_1^2$）。**用 $e_1^2 = d\,e_1$ 展开（$A$ 是标量）：

$$
\rho_A(\sigma_1^2) = \left(A + A^{-1}e_1\right)^2
= A^2 + 2e_1 + A^{-2}e_1^2
= A^2\,I + \left(2 + A^{-2}d\right)e_1 .
$$

闭合读出（恒等图 $\mapsto d$、$e_1$ 图 $\mapsto 1$）：

$$
\langle\widehat{\sigma_1^2}\rangle = A^2 d + 2 + A^{-2}d
= d\left(A^2 + A^{-2}\right) + 2
= -\left(A^2+A^{-2}\right)^2 + 2
= -A^4 - A^{-4},
$$

（第三个等号代入 $d = -(A^2+A^{-2})$，末步展开平方。）与文献中 Hopf 链环的括号值一致。换到 Jones：闭合图有 $w = 2$ 个正交叉，

$$
V_{\text{Hopf}} = (-A)^{-6}\left(-A^4 - A^{-4}\right)
= A^{-6}\left(-A^4-A^{-4}\right)
= -A^{-2} - A^{-10}
= -t^{1/2} - t^{5/2}.
$$

在根值处：$A^4 + A^{-4} = 2\cos(\pi/3) = 1$，故 $\langle\widehat{\sigma_1^2}\rangle = -1$；而

$$
V_{\text{Hopf}}\!\left(e^{i\pi/3}\right)
= -e^{i\pi/6} - e^{i5\pi/6}
= -\left(\tfrac{\sqrt3}{2}+\tfrac i2\right) - \left(-\tfrac{\sqrt3}{2}+\tfrac i2\right)
= -i .
$$

顺带一提，二分量平凡链环的值是 $-t^{1/2}-t^{-1/2} = -2\cos(\pi/6) = -\sqrt3 = d$（环值亲自现身），而 Hopf 的镜像给出 $+i$：**这个根值足以区分 Hopf 与平凡链环、以及两种手性**。

**第四步：三叶结（$b=\sigma_1^3$）。**同法展开（二项式型求和，$e_1^j = d^{j-1}e_1$）：

$$
\rho_A(\sigma_1^3) = A^3 + \left(3A + 3A^{-1}d + A^{-3}d^2\right)e_1 .
$$

闭合：

$$
\langle\widehat{\sigma_1^3}\rangle = A^3 d + 3A + 3A^{-1}d + A^{-3}d^2 .
$$

逐项代入 $d = -A^2 - A^{-2}$ 并展开：$A^3d = -A^5 - A$；$3A^{-1}d = -3A - 3A^{-3}$；$A^{-3}d^2 = A^{-3}(A^4+2+A^{-4}) = A + 2A^{-3} + A^{-7}$。求和（$A$ 的系数 $-1+3-3+1=0$，$A^{-3}$ 的系数 $-3+2=-1$）：

$$
\langle\widehat{\sigma_1^3}\rangle = -A^5 - A^{-3} + A^{-7},
$$

与文献中三叶结的括号值完全一致。Jones 值（$w = 3$，$(-A)^{-9} = -A^{-9}$）：

$$
V_{\text{trefoil}} = -A^{-9}\left(-A^5 - A^{-3} + A^{-7}\right)
= A^{-4} + A^{-12} - A^{-16}
= t + t^3 - t^4 .
$$

（每一步只用 $A^{-9}\cdot A^{5} = A^{-4}$ 型的指数加法。）在根值处：

$$
V_{\text{trefoil}}\!\left(e^{i\pi/3}\right)
= e^{i\pi/3} + e^{i\pi} - e^{i4\pi/3}
= \left(\tfrac12+\tfrac{\sqrt3}{2}i\right) + (-1) - \left(-\tfrac12-\tfrac{\sqrt3}{2}i\right)
= i\sqrt3 .
$$

镜像三叶结（把 $A$ 与 $A^{-1}$ 互换的约定）在同一根处取值 $-i\sqrt3$。

**第五步：算法视角复盘。**量子算法在这个例子上做什么？它**不**展开上面的代数，而是：

1. 编译：$\rho_A(\sigma_1^3) = A^3 I + (\cdots)e_1$ 作为二维空间上的酉矩阵 $U_b$ 由三个局部门（每个对应一个 $\sigma_1$）实现；
2. 制备 cup 态 $|\alpha\rangle$（或提纯态 $|\sqrt\pi\rangle$，权重 $\lambda_1:\lambda_3 = 1:2$）；
3. Hadamard test 测 $\operatorname{Re}\langle\alpha|U_b|\alpha\rangle$ 与虚部，$K = \Theta(1/\epsilon^2)$ 次运行得加性 $\epsilon$；
4. 乘上经典可算的 $C(b,6)$（含 $(-A)^{-9}$、圈数幂与态归一化），得到 $i\sqrt3$ 的 $|C|\epsilon$ 加性近似。

我们上面用纯经典的手算**交叉验证了**第 4 步的目标值。规模增大时，手算的项数指数增长（$\rho_A(b)$ 的 TL 展开有指数多项），而量子电路仍是 $m$ 个门的乘积——这就是“指数经典、多项式量子”差距的具体形状。同时注意本例的 $|C|$ 是常数阶，加性近似足以区分 $\pm i\sqrt3$（相差 $2\sqrt3$）；对一般输入，第 5.4 节的告诫仍然全部有效。

## 9. 更远的一步：HOMFLY 与 Khovanov 同调

### 9.1 Hecke 代数与 HOMFLY

Jones 多项式有一个双变量推广 **HOMFLY 多项式** $P_L(a,z)$（以发现者姓名首字母命名），它同时单变量化为 Jones 与 Alexander 多项式。表示论上，把 Temperley--Lieb 代数换成 **Hecke 代数**（对称群代数的 $q$-形变；TL 代数是它的一个商），同一套“辫 $\to$ 代数表示 $\to$ 矩阵元/迹”的机器原样运转：HOMFLY 在适当参数点上同样可以被量子算法做加性近似（Zoo 93 一线的工作）。再往外，quantum double（Drinfeld double）构造给出另一族链环不变量（Zoo 174），其算法面貌与本章 [三维流形不变量](three-manifold-invariants.md) 一课的 Turaev--Viro/Reshetikhin--Turaev 状态和同源。这一族推广的共同结构是：**“结的拓扑 $\leftrightarrow$ 某个代数的表示论 $\leftrightarrow$ 酉矩阵元”三层字典**，本课第 3--5 节建立的正是其中最简单的一层。

(khovanov-homology)=
### 9.2 范畴化：Khovanov 同调

2000 年，Khovanov 对 Jones 多项式做了**范畴化 (categorification)**：构造一族分次阿贝尔群——**Khovanov 同调** $Kh^{i,j}(L)$——使其分次 Euler 特征标恢复 Jones 多项式（差一个已知的移位与线性替换），而同调群本身携带严格更多的信息。构造的形状：

- **链群**：对结图的每个交叉选一种平滑（共 $2^c$ 种选择，称为 Kauffman 状态），每个状态按圈数与平滑类型获得双分次 $(i,j)$，生成分次自由阿贝尔群。链空间维数 $\sum\dim C^{i,j}$ 是 $2^c$ 量级——**指数大**。
- **边缘算子**：$d:C^{i,j}\to C^{i,j+1}$（合并/分裂圈的标准映射配上符号安排），满足 $d^2 = 0$（符号安排的相容性需要验证，这是构造的技术核心）。
- **同调**：

$$
Kh^{i,j} = \ker d_{i,j}\,/\,\operatorname{im} d_{i-1,j},
$$

闭链模边缘链。分次 Euler 特征标 $\sum_{i,j}(-1)^i q^j\dim Kh^{i,j}$（把维数放进生成函数）恢复 Jones。

信息量的差距是实质性的：存在 Jones 多项式相同而 Khovanov 同调不同的链环对；Khovanov 同调能识别平凡结（同调的秩达到平凡结的最小值就蕴含链环平凡——这是已被证明的定理；而 Jones 多项式是否也能识别平凡结，即 $V_L = 1$ 是否蕴含 $L$ 平凡，至今是未解决问题）。因此“算 Khovanov 同调”是严格更强的算法问题。复杂性一侧，精确计算当然至少和 Jones 一样难；2025 年的工作（Zoo 510--511）进一步把**秩的加性近似**按精度分了档：越来越精确的加性近似分别是 DQC1-hard、BQP-hard、$\#\mathsf{P}$-hard——精度档位每提高一级，难度上升一个世界，这与第 5.4 节“加性 vs 相对 vs 精确”的阶梯精确呼应。

### 9.3 Hodge Laplacian 方案与它的条件

2025 年的量子算法（arXiv:2501.12378）把同调秩的计算化为一个谱问题。核心是**Hodge Laplacian**

$$
\Delta := d^\dagger d + d d^\dagger ,
$$

其中 $d^\dagger$ 是边缘算子关于链空间标准内积的伴随。

**Lemma 6（调和代表）**. $\ker\Delta = \ker d \cap \ker d^\dagger$，且其维数等于同调维数（Betti 数 / Khovanov 秩）。

**证明**。设 $c\in\ker\Delta$。计算（用 $d,d^\dagger$ 自伴、$dd^\dagger$ 与 $d^\dagger d$ 半正定）：

$$
0 = \langle c,\Delta c\rangle = \langle c,d^\dagger dc\rangle + \langle c,dd^\dagger c\rangle
= \langle dc,dc\rangle + \langle d^\dagger c,d^\dagger c\rangle
= \|dc\|^2 + \|d^\dagger c\|^2 .
$$

（第二个等号：$\langle c,d^\dagger(dc)\rangle = \langle dc,dc\rangle$，这是伴随的定义；第三项同理。）范数平方非负且和为零，故 $dc = 0$（闭）且 $d^\dagger c = 0$（余闭）。反之闭且余闭的 $c$ 显然被 $\Delta$ 消灭。于是 $\ker\Delta$ = 闭且余闭的链（**调和链**）。每个同调类 $[c]$ 有唯一的调和代表（Hodge 分解 $c = h + d\alpha + d^\dagger\beta$），映射 $[c]\mapsto h$ 是同调群到调和链空间的同构，故维数相等。Q.E.D.

**算法的形状。**于是“算 $\dim Kh$”变成“算 $\Delta$ 的零空间维数”。由于链空间维数指数大，不能直接对角化；方案是估计 $\Delta$ 的**近零谱质量**——零空间占全空间的比例：

- **Gibbs / 相位估计提取**：制备 Hodge Laplacian 的 Gibbs 态 $e^{-\beta\Delta}/\operatorname{Tr}e^{-\beta\Delta}$（或对 $e^{-i\beta\Delta}$ 做相位估计），测量“能量近零”的概率，它近似 $\dim\ker\Delta$ 与全维数之比。Gibbs 态制备与相位估计分别关联本站第 6 章（Gibbs 态制备）与第 3 章（相位估计）的工具，谱隙决定所需分辨精度。
- **预热化 (pre-thermalization)**：若 Betti 数远小于链空间维数（同调极小、链群巨大——一般情形正是如此），近零谱质量指数小，直接采样测不到。预热化步骤先把态**集中到近零/低能子空间**附近再做 Gibbs/相位估计提取，专门克服“秩 $\ll$ 维数”的失衡——这是该工作相对先前量子同调算法的关键改进。

**适用条件（务必保留的条款）。**论文声明的高效性依赖两个承诺，并有数值与解析证据支持、但不是无条件定理：

1. **可热化**：$\Delta$ 的 Gibbs 态能在多项式时间内制备（典型 Gibbs 制备的障碍——谱隙、温度、与环境的耦合设计——这里全部内嵌于“thermalize”一词，见第 6 章 Gibbs 态一课的讨论）；
2. **谱隙**：零空间（严格说零特征值簇）与其余谱之间有 $\ge 1/\operatorname{poly}$ 的间隙，否则相位估计无法在多项式时间内把“近零”与“非零”分开。

**没有这些条件时**：链空间指数大、同调秩可能极小，近零质量被指数压制，任何基于谱估计的方案都需要指数资源——**不能宣称普适的指数加速**。与第 5.4 节 Jones 的处境对照：一边是“归一化尺度的加性近似”，一边是“热化与谱隙承诺下的秩估计”，两者都以“精确说明自己买到了什么”为底线，这正是本章导言的原则在本课的两次落地。

## 10. 小结

**小结。**

- 结图的 Kauffman 括号由三条规则定义（归一化、脱圈 $d = -A^2-A^{-2}$、交叉展开），经 writhe 补偿因子 $(-A)^{-3w}$ 后给出 Jones 多项式；R2/R3 不变性恰好化为 Temperley--Lieb 代数的恒等式。
- 链环经 Alexander 定理化成 braid word（长度 $m$、股数 $n$）；$\rho_A(\sigma_i) = A I + A^{-1}e_i$ 是 braid 群表示**当且仅当** $d = -(A^2+A^{-2})$（Lemma 1--3 的计算），这也是括号的拓扑自洽条件与酉性条件（Lemma 5）——同一个等式出现三次。
- 单位根 $t = e^{2\pi i/k}$、$A = t^{-1/4}$ 处，$d = -2\cos(\pi/k)$ 与路径图 $A_{k-1}$ 的谱半径重合，Perron--Frobenius 权重 $\lambda_j = \sin(\pi j/k)$（和差化积恒等式）构造出使 $e_i$ 自伴的路径表示；braid word 编译为 $\operatorname{poly}(m,n,k)$ 的局部酉电路（因子 $m,n,k$ 的来源逐项清点于第 4.4 节）。
- **Plat closure = 矩阵元**：Hadamard test 以 $\Theta(1/\epsilon^2)$ 采样（Hoeffding）或振幅估计 $O(1/\epsilon)$ 给出 $\langle\alpha|U_b|\alpha\rangle$ 的加性 $\epsilon$ 估计；Jones 值的误差是 $|C(b,k)|\epsilon$——加性、非相对、非精确，且 $|C|$ 可指数大（第 5.4 节）。
- **Trace closure = Markov trace**：终点权重 $\pi(p)\propto\lambda_{p_n}$ 的加权归一化迹（Markov 定理迫使的形状）；可经提纯态一次 Hadamard test 估计，或两阶段抽样（第 6.2 节给出 $s^* = \sigma_\pi\sqrt N/c$ 的平衡解）；归一化迹是 DQC1 的母语，某些 trace-closure 近似 DQC1-complete（Shor--Jordan）。
- plat closure 的加性近似在适当固定的 $k$（如 $k=5$，Fibonacci 型稠密表示）下 **BQP-complete**（AJL + Freedman--Larsen--Wang + Solovay--Kitaev 编译）；完备性绑定特定根、closure 与误差尺度。
- Khovanov 同调范畴化 Jones（分次 Euler 特征标恢复之、信息严格更多）；2025 年方案把秩计算化为 Hodge Laplacian $\Delta = d^\dagger d + dd^\dagger$ 的近零谱质量（$\ker\Delta \cong$ 同调，Lemma 6），以预热化克服“秩 $\ll$ 维数”，高效性依赖多项式热化与谱隙承诺；秩的加性近似按精度分为 DQC1-hard / BQP-hard / $\#\mathsf{P}$-hard 三档。

## 练习题

**练习 1【Kauffman 括号与 Jones 多项式】**（→ [1.2 节](#kauffman-bracket-jones)）

1. 写出 Kauffman 括号的三条规则；计算两个不相交圆圈（二分量平凡链环，$w=0$）的括号值，并换元写出它的 Jones 值。
2. 说明一次 R1 移动（增删一个卷）如何让 $\langle D\rangle$ 乘上 $-A^{\pm3}$、同时让 $w(D)$ 变化 $\pm1$，从而解释补偿因子 $(-A)^{-3w(D)}$ 为何使 $f_D(A)$ 在 R1 下不变。

> 提示：第 2 题中一个卷自身的括号是 $-A^{\pm3}$（第 8 节第二步有完整数圈计算），恰好被 $(-A)^{\mp3}$ 抵消。

**练习 2【辫群与两种闭合】**（→ [2.2 节](#braid-closures)）

1. 写出 $B_n$ 的生成元与两条定义关系；计算 $b=\sigma_1^2\sigma_2^{-1}$ 的指数和 $w(b)$，并指出 2 股辫 $\sigma_1^m$ 的 trace closure 是哪一族链环、$m=2$ 与 $m=3$ 各是什么。
2. 解释 plat closure 与 trace closure 分别把链环不变量对应到“固定初态上的矩阵元”与“（加权）迹”的原因（杯—帽初态、“第 $i$ 股接回第 $i$ 股即对股指标求和”两个角度），并由此说明 AJL 与 Shor--Jordan 的完备性结论为何分别落在 BQP 与 DQC1 两个模型。

> 提示：对照第 5.1 节与第 6.1、6.3 节的读出公式；DQC1 的母语正是归一化迹。

**练习 3【Temperley--Lieb 代数与表示定理】**（→ [3.1 节](#tl-algebra-representation)）

1. 用 $e_i^2 = d\,e_i$ 展开 $\left(AI + A^{-1}e_i\right)\left(A^{-1}I + Ae_i\right)$，写出结果并指出它等于 $I$ 的条件。
2. **（TL 图示演算）**画图验证第 3.1 节的三条 TL 关系：(a) 对 $e_i^2 = d\,e_i$，数出堆叠中封闭圈的个数并说明为何恰好是一个；(b) 对 $e_ie_{i+1}e_i = e_i$，追踪三条外侧股的连通情况，说明中间为何没有产生封闭圈；(c) 用 (a)(b) 复核第 3.3 节 Lemma 3 展开中 $u^2 = du$ 与 $uvu = u$ 的每次使用。

> 提示：第 1 题就是第 3.3 节 Lemma 1 的计算；第 2 题只需要数圈与追踪端点的连通性。

**练习 4【单位根与 path model 酉表示】**（→ [4.1 节](#unitary-path-model)）

1. 取 $k=6$：写出 $A^2$ 与环值 $d$，验证 $A^2+A^{-2}+d=0$，并列出 $A_5$ 的 Perron--Frobenius 权重 $\lambda_j=\sin(\pi j/6)$（$j=1,\dots,5$）与谱半径。
2. 设 $e$ 自伴、$e^2=de$、$|A|=1$。证明 $U=AI+A^{-1}e$ 满足 $UU^\dagger = I+(A^2+A^{-2}+d)e$，并给出 $U$ 酉的充要条件。
3. 验证 $\lambda_j=\sin(\pi j/k)$ 是路径图 $A_{k-1}$ 邻接矩阵以 $2\cos(\pi/k)$ 为特征值的特征向量：内部顶点用和差化积恒等式、端点用二倍角公式分别核对。

> 提示：第 2 题用 $|A|=1\Rightarrow\bar A=A^{-1}$ 与自伴性；第 3 题端点处的方程即 $\sin(2\pi/k)=2\sin(\pi/k)\cos(\pi/k)$。

**练习 5【Hadamard test 与加性近似】**（→ [5.2 节](#hadamard-test-additive-approximation)）

1. 从 $|\Psi_2\rangle=\frac{1}{\sqrt2}\left(|0\rangle|\alpha\rangle+|1\rangle U_b|\alpha\rangle\right)$ 出发，计算辅助比特的 $\langle X\rangle$ 与 $\langle Y\rangle$，并写出概率 $p_+$ 与 $\operatorname{Re}a$ 的关系式。
2. **（采样置信度）**第 5.3 节用 Hoeffding 不等式得到常数置信度下 $K = \Theta(1/\epsilon^2)$。若要求置信度 $1-\delta_{\rm conf}$，写出 $K$ 关于 $\epsilon$ 与 $\delta_{\rm conf}$ 的完整表达式，并解释为什么对 $\delta_{\rm conf}$ 的依赖只是对数级的（联系振幅估计中“失败重试”的标准论证）。
3. **（误差尺度）**设某链环的 $|C(b,k)| = 2^{m/2}$、而 $|J| \approx 1$。(a) 要让加性估计足以判断 $J$ 的符号，$\epsilon$ 需多小？采样复杂度随 $m$ 如何增长？(b) 由此解释为什么“加性近似 BQP-complete”与“相对误差近似可能需要指数资源”并不矛盾，并说明这与第 5.4 节、第 9.3 节两处保留条款的关系。

> 提示：第 1 题展开后用 $\langle0|1\rangle=0$ 消去辅助比特指标不同的项；第 3 题 (a) 需要 $\epsilon|C|$ 小于 $|J|$ 的量级。

**练习 6【Markov trace 与 DQC1】**（→ [6.2 节](#markov-trace-dqc1)）

1. 写出 Markov trace 的公式与权重 $\pi(p)\propto\lambda_{p_n}$，并解释共轭不变与稳定化不变分别为何迫使它是“迹”与“只依赖终点的加权”。
2. 验证 $\langle\sqrt{\pi}|\,U_b\,|\sqrt{\pi}\rangle=\sum_p\pi(p)\langle p|U_b|p\rangle=\operatorname{Tr}_{\rm Markov}(U_b)$，并说明用哪条性质消去了交叉项。
3. **（两阶段平衡）**在第 6.2 节的两阶段方案中，设 $\sigma_\pi = 3$、$c = 1$、总预算 $N = 10^6$ 次电路运行。求最优的 $s^*,K^*$ 与相应的总误差；若把预算提高为 $4N$，误差改善多少？由此说明“把样本在两个阶段间按 $\sigma_\pi : c$ 分配、使两项误差同阶”的含义。

> 提示：第 2 题用路径基正交归一性 $\langle p|q\rangle=\delta_{pq}$；第 3 题可代回 $f(s^*)=2\sqrt{\sigma_\pi c}\,/N^{1/4}$ 检验。

**练习 7【手算例子：Hopf 链环与三叶结】**（→ [第 8 节](#worked-example-k6)）

1. 用“恒等图闭合得两个圈、$e_1$ 图闭合得一个圈”的数圈规则计算 $\langle\widehat{\sigma_1}\rangle$，验证它等于 $-A^3$，并说明乘上补偿因子后平凡结的 $V=1$。
2. **（计算）**沿第 8 节的方法计算 $\rho_A(\sigma_1^4)$（提示：$(A+A^{-1}e)^4 = A^4 + \big(\sum_{j=1}^{4}\binom4j A^{4-2j}d^{j-1}\big)e$，逐项写出）与 $\langle\widehat{\sigma_1^4}\rangle$，并求 trace closure（$(2,4)$ 环面链环）的 Jones 值在 $t = e^{2\pi i/6}$ 处的显式复数。再用 $V_{\widehat{\sigma_1^2}} = -i$ 与 skein 关系 $t^{-1}V_{L_+} - tV_{L_-} = (t^{1/2}-t^{-1/2})V_{L_0}$ 核对你的答案。

**练习 8【范畴化：Khovanov 同调】**（→ [9.2 节](#khovanov-homology)）

1. 描述 Khovanov 链群的构造：$2^c$ 个 Kauffman 状态如何给出双分次 $(i,j)$ 与链群，并写出分次 Euler 特征标 $\sum_{i,j}(-1)^iq^j\dim Kh^{i,j}$ 恢复 Jones 多项式的关系。
2. **（概念辨析）**分别给出以下三个量能区分、而前一个不能区分的链环例子或论证方向：(a) Jones 多项式 vs Khovanov 分次 Euler 特征标（它们何时给出相同信息？）；(b) Euler 特征标 vs Khovanov 同调群（提示：同一组分次维数可以给出相同 Euler 特征标而群结构不同；再想想“识别平凡结”的性质落在哪一侧）；(c) 结合第 9.2 节的三档硬度阶梯，说明“把秩估计到越来越准”为什么在每个档位上落进不同的复杂度类。
3. 解释为什么“计算 $\dim Kh$”可以化为“估计 Hodge Laplacian $\Delta=d^\dagger d+dd^\dagger$ 的近零谱质量”，并指出该方案高效性依赖的两个承诺（可热化与谱隙）分别排除什么障碍。

> 提示：第 3 题从 $\ker\Delta=\ker d\cap\ker d^\dagger$、其维数等于同调维数（第 9.3 节 Lemma 6）出发。

## 参考文献与 Zoo 覆盖

- Zoo 2、4、41、42：[Aharonov--Jones--Landau](https://arxiv.org/abs/quant-ph/0511096) 与 TQFT universality/BQP-hardness。
- Zoo 83、93、174：DQC1 trace closure、HOMFLY 与 quantum-double link invariants。
- Zoo 3：Tutte/Potts 推广。
- Zoo 510--511：cohomology complexity 与 [Khovanov homology 量子算法](https://arxiv.org/abs/2501.12378)。