量子结与链环不变量

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 的编织做[通用量子门](../fundamentals/universal-gate-set)），也隐含了“逼近 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 及本词条 配分函数量子算法 词条。2025 年，Schmidhuber 等人给出了第一个 Khovanov 同调的量子算法（Zoo 510—511），其核心是把同调秩的计算化为 Hodge Laplacian 近零谱质量的估计。

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

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 括号正是这样被逐条验证的。

1.2 Kauffman 括号与 Jones 多项式

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

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

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

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

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

$$f_D(A):=(-A{)}^{-3w(D)}⟨D⟩.$$

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

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

它也等价地由 Jones 原始的 skein 关系 $t^{-1}{V}_{L_{+}}-t{V}_{L_{-}}=(t^{1/2}-t^{-1/2})V_{L_0}$（配合 $V_{◯}=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 多项式在相应点读出（媒介构造见本词条 配分函数量子算法 第 5 节）。而 Jaeger—Vertigan—Welsh 的一族结果表明，Tutte 多项式在大多数固定点上的精确求值是 $\#\mathsf{P}$-hard 的；相应地，Jones 多项式在大多数固定求值点上的精确计算也被证明（或普遍相信，视具体点集而定）落在同样的难度量级。只有少数特殊点（如 $t=\pm 1$ 等退化情形）已知有多项式时间经典算法。本词条反复出现的告诫在这里原样适用：$\#\mathsf{P}$-hard 的精确量不会被任何通用多项式算法（经典或量子）解决。

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

1.4 本词条路线图

1. 第 2 节：把链环输入代数化为 braid word，区分 trace closure 与 plat closure 两种读出方式；
2. 第 3 节：Temperley—Lieb 代数与 Kauffman 的字典“交叉 $=$ 平滑的线性组合”，验证 ${\rho }_A$ 确实是 braid 群表示；
3. 第 4 节：在单位根上构造 path model，使表示变酉，并逐项解释 $\mathrm{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(|i-j|\ge 2),{\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{ϵ}_j$，其中 ${ϵ}_j\in \{\pm 1\}$。第 1.2 节的 writhe 对“全部股向下定向”的辫图恰好等于 $w(b)$——这个量稍后将进入归一化因子。

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 ⟩$），链环的不变量正比于辫表示算子在该态上的矩阵元 $⟨\alpha |U_b|\alpha ⟩$。矩阵元用一次 Hadamard test 就能采样——这是 AJL 算法的读出，也是 BQP 完备性的载体。
• trace closure $\Rightarrow$ 迹。闭合把“第 $i$ 股接回第 $i$ 股”翻译成“对股指标求和”，对应表示算子的（加权）迹。归一化迹是 DQC1 模型的母语（第 6.3 节），这是 Shor—Jordan 结果的载体。

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

$$b={\sigma }_{i_1}^{{ϵ}_1}{\sigma }_{i_2}^{{ϵ}_2}\cdots {\sigma }_{i_m}^{{ϵ}_m},1\le i_j\le n-1,{ϵ}_j\in \{\pm 1\},$$

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

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

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,e_i{e}_{i\pm 1}{e}_i=e_i,e_i{e}_j=e_j{e}_i(|i-j|\ge 2).$$

逐条解释为什么成立：

• $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$。这是三条中最需要画图核对的一条，留作习题 1 让读者把连通分支数出来。
• 远交换律：$e_i$ 与 $e_j$ 触及的端点集 $\{i,i+1\}$ 与 $\{j,j+1\}$ 不相交（$|i-j|\ge 2$），堆叠次序显然无关。

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

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

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

$${\rho }_A({\sigma }_i):=AI+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(AI+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|\ge 2$ 成立，对任意 $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{array}{rl}\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{array}$$

（逐项来源：$A\cdot A\cdot A=A^3$；两次“$IIu$”各贡献 $Au$；“$IvI$”贡献 $Av$；“$Ivu$”与“$uvI$”各贡献 $A^{-1}$ 倍的 $vu,uv$；“$uIu$”贡献 $A^{-1}{u}^2=A^{-1}du$；“$uvu$”贡献 $A^{-3}uvu=A^{-3}u$，最后一步用了 $e_i{e}_{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^{\pm 1}$ 映为上述可逆元素）；并且此时括号在 R2 移动下的不变性（Lemma 1 的恒等式）与 R3 移动下的不变性（Lemma 3 的恒等式）逐条成立，R1 的亏损恰好是 $(-A{)}^{\pm 3}$ 因子，被 $(-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$ 的幂。由线性性，

$$⟨\hat{b}⟩=\text{（把 }{\rho }_A(b)\text{ 中每个图闭合、数圈、加权求和）}，$$

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

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

4.1 酉性引理

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

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

$$U:=AI+A^{-1}e$$

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

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

$$U{U}^{†}=\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$，则 $U{U}^{†}=I$，且同理 $U^{†}U=I$，$U$ 酉。反之，若 $U$ 酉则 $U{U}^{†}=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\ge 3$（后文称 level），取

$$t=e^{2\pi i/k},A=t^{-1/4},\text{于是}{A}^2=e^{-\pi i/k},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),j=1,\dots ,k-1.$$

这两句话可以直接验证：顶点 $j$ 的两个邻居是 $j\pm 1$（端点 $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},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 =(\frac{1}{2},\frac{\sqrt{3}}{2},1,\frac{\sqrt{3}}{2},\frac{1}{2})$、谱半径 $\sqrt{3}$，与 $|d|=\sqrt{3}$ 一致。

${\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),p_0=1,|p_{j+1}-p_j|=1,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 ⟩$：其支集集中在“路径在相邻高度间规则往返”的路径上（每个杯位强迫一次上—下往返）。这样的态由位置的奇偶性确定，是浅层电路可制备的乘积型态。

4.4 电路复杂度：逐项清单

把 braid word $b={\sigma }_{i_1}^{{ϵ}_1}\cdots {\sigma }_{i_m}^{{ϵ}_m}$ 编译成量子电路 $U_b:={\rho }_A(b)$，按从右到左逐个执行 ${\rho }_A({\sigma }_{i_j}{)}^{{ϵ}_j}$。总规模 $\mathrm{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)$ 个常数（实现时取足够精度的定点近似）；合法性判定需要知道“高度是否在 $\mathrm{1..}k-1$ 内”，涉及 $\log k$ 个比特。
• 辅助：Hadamard test 需要额外 $1$ 个比特（第 5.2 节）。

所以：电路大小 $\mathrm{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_{\mathrm{plat}(b)}\left(e^{2\pi i/k}\right)=C(b,k)⟨\alpha |U_b|\alpha ⟩,$$

其中三个符号的含义：

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

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

5.2 Hadamard test 的完整推导

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

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

$$|{\Psi }_1⟩=\frac{1}{\sqrt{2}}\left(|0⟩+|1⟩\right)|\alpha ⟩.$$

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

$$|{\Psi }_2⟩=\frac{1}{\sqrt{2}}\left(|0⟩|\alpha ⟩+|1⟩U_b|\alpha ⟩\right).$$

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

$$⟨{\Psi }_2|X\otimes I|{\Psi }_2⟩=\frac{1}{2}\left(⟨\alpha |⟨0|+⟨\alpha |U_b^{†}⟨1|\right)\left(|1⟩|\alpha ⟩\cdot 1+|0⟩U_b|\alpha ⟩\cdot 1\right)$$

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

$$=\frac{1}{2}\left(⟨\alpha |U_b|\alpha ⟩+⟨\alpha |U_b^{†}|\alpha ⟩\right)=\frac{1}{2}\left(a+\bar{a}\right)=\mathrm{Re}a.$$

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

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

$$⟨{\Psi }_2|Y\otimes I|{\Psi }_2⟩=\frac{1}{2}\left((-i)⟨\alpha |U_b|\alpha ⟩+(i)⟨\alpha |U_b^{†}|\alpha ⟩\right)=\frac{i}{2}\left(\bar{a}-a\right)=\mathrm{Im}a.$$

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

$$\mathrm{Re}a=2p_{+}-1,\mathrm{Im}a=⟨Y⟩,$$

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

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

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

$$\mathrm{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 =ϵ/2$（这样 $|2\hat{p}-1-\mathrm{Re}a|\le 2\delta =ϵ$），得实部到加性 $ϵ$ 需要

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

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

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

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

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

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

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

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

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

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

• **$|C(b,k)|$ 可以关于 $m$ 指数大。**它包含 $d$ 的幂（每多一个闭合圈贡献一个 $d$，$d$ 的模是常数但幂次随 $n,m$ 增长）与 framing 因子。于是“矩阵元的 $ϵ$ 加性近似”换算到 Jones 值是“尺度 $|C|$ 上的加性近似”——若 $|C|$ 指数大，绝对误差 $ϵ|C|$ 对典型的 Jones 值可能毫无信息量。
• **它不是相对误差。**相对误差要求 $|\hat{J}-J|\le ϵ|J|$；对 $|J|\ll |C|$ 的链环，由 $|J|=|C||a|$ 可知这要求 $ϵ\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^{\prime }\in B_{n^{\prime }}$ 的 trace closure 同痕，当且仅当它们可通过两类移动互变：共轭（$b\mapsto xb{x}^{-1}$，同群内）与稳定化（$b\mapsto b{\sigma }_n^{\pm 1}\in B_{n+1}$，加一股打一次交叉）。要在表示论一侧得到链环的泛函，必须找到一个对这两类移动不变（差已知因子）的线性泛函：

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

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

$${\mathrm{Tr}}_{\mathrm{Markov}}(U_b)=\sum _p\pi (p)⟨p|U_b|p⟩,\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 配平。

6.2 两条实现路线与一个参数平衡

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

$$|\sqrt{\pi }⟩:=\sum _p\sqrt{\pi (p)}|p⟩$$

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

$$⟨\sqrt{\pi }|U_b|\sqrt{\pi }⟩=\sum _{p,q}\sqrt{\pi (p)\pi (q)}⟨q|U_b|p⟩\cdot ⟨p|q⟩=\sum _p\pi (p)⟨p|U_b|p⟩={\mathrm{Tr}}_{\mathrm{Markov}}(U_b),$$

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

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

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

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

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

$$f^{\prime }(s)=-\frac{{\sigma }_{\pi }}{2}{s}^{-3/2}+\frac{c}{2\sqrt{N}}{s}^{-1/2}=0⟹\frac{c}{2\sqrt{N}}{s}^{1/2}=\frac{{\sigma }_{\pi }}{2}{s}^{-1/2}⟹s^{\ast }=\frac{{\sigma }_{\pi }\sqrt{N}}{c},K^{\ast }=\frac{N}{s^{\ast }}=\frac{c\sqrt{N}}{{\sigma }_{\pi }}.$$

代回得 $f(s^{\ast })=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 }⟩$，只剩量子测量噪声一项，误差回到 $N^{-1/2}$（即 $1/{ϵ}^2$ 采样）。这就是提纯优于两阶段抽样的定量理由。

6.3 DQC1：归一化迹的母语

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

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

$${\rho }_0=|0⟩⟨0|\otimes \frac{I}{2^n}.$$

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

$${\rho }^{\prime }=\frac{1}{2^{n+1}}\left(|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes I+|0⟩⟨1|\otimes U^{†}+|1⟩⟨0|\otimes U\right).$$

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

$${\rho }_{\mathrm{clean}}^{\prime }=\frac{1}{2}\left(\begin{array}{cc}1& \bar{\tau }\\ \tau & 1\end{array}\right),⟨X⟩=\mathrm{Re}\tau ,⟨Y⟩=\mathrm{Im}\tau .$$

（最后两个等号：$\mathrm{Tr}({\rho }_{\mathrm{clean}}^{\prime }X)=\frac{1}{2}(\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/\mathrm{poly}$ 精度”），得到：任何量子电路都可以被经典多项式时间编译成一个多项式长度的 braid word $b_C$。（AJL 文的表述即：其算法在五次单位根 $e^{2\pi i/5}$ 处解决的是 BQP-complete 问题，依据正是 Freedman 等人的结果。）

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

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

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

**拼起来的归约。**假设存在（经典或量子）算法 $\mathcal{A}$ 能在 AJL 指定的归一化尺度内加性逼近 $⟨\alpha |\rho (b_C)|\alpha ⟩$。给定任意 BQP 电路 $C$：经典多项式时间编译出 $b_C$，运行 $\mathcal{A}$，乘上已知尺度读出 $⟨0|C|0⟩$ 的近似——精度取到足以区分“接受概率 $\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 节）。同章 三维流形不变量 词条对 Turaev—Viro 不变量的 BQP-complete 结论有平行的讨论，可对照阅读。

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}=-\sqrt{3}.$$

注意 $|d|=\sqrt{3}=2\cos (\pi /6)$ 恰是 $A_5$ 的谱半径（第 4.2 节），且 ${\lambda }_1=\sin (\pi /6)=\frac{1}{2}$、${\lambda }_3=\sin (\pi /2)=1$。两股（$n=2$）的合法路径只有

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

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

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

$$A+A^{-1}d=e^{-i\pi /12}\left(1-\sqrt{3}{e}^{i\pi /6}\right)=e^{-i\pi /12}\cdot e^{-i2\pi /3}=e^{-i3\pi /4},|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)=AI+A^{-1}{e}_1$。把两项分别 trace-close：恒等图（两条竖线）闭合后是两个不相交圆圈（每条竖线与自己的闭合弧成一圈），括号 $d$；$e_1$（上弧接上弧、下弧接下弧）闭合后是一个圆圈，括号 $1$。所以

$$⟨\widehat{{\sigma }_1}⟩=A\cdot d+A^{-1}\cdot 1=\left(-A^3-A^{-1}\right)+A^{-1}=-A^3.$$

这正是第 1.2 节预言的单卷行为（$⟨\text{卷}⟩=-A^{\pm 3}$），与“补偿因子 $(-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$）：

$$⟨\widehat{{\sigma }_1^2}⟩=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$，故 $⟨\widehat{{\sigma }_1^2}⟩=-1$；而

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

顺带一提，二分量平凡链环的值是 $-t^{1/2}-t^{-1/2}=-2\cos (\pi /6)=-\sqrt{3}=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.$$

闭合：

$$⟨\widehat{{\sigma }_1^3}⟩=A^{3}d+3A+3A^{-1}d+A^{-3}{d}^2.$$

逐项代入 $d=-A^2-A^{-2}$ 并展开：$A^{3}d=-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$）：

$$⟨\widehat{{\sigma }_1^3}⟩=-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(\frac{1}{2}+\frac{\sqrt{3}}{2}i\right)+(-1)-\left(-\frac{1}{2}-\frac{\sqrt{3}}{2}i\right)=i\sqrt{3}.$$

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

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

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

我们上面用纯经典的手算交叉验证了第 4 步的目标值。规模增大时，手算的项数指数增长（${\rho }_A(b)$ 的 TL 展开有指数多项），而量子电路仍是 $m$ 个门的乘积——这就是“指数经典、多项式量子”差距的具体形状。同时注意本例的 $|C|$ 是常数阶，加性近似足以区分 $\pm i\sqrt{3}$（相差 $2\sqrt{3}$）；对一般输入，第 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），其算法面貌与本词条 三维流形不变量 词条的 Turaev—Viro/Reshetikhin—Turaev 状态和同源。这一族推广的共同结构是：“结的拓扑 $\leftrightarrow$ 某个代数的表示论 $\leftrightarrow$ 酉矩阵元”三层字典，本词条第 3—5 节建立的正是其中最简单的一层。

9.2 范畴化：Khovanov 同调

2000 年，Khovanov 对 Jones 多项式做了范畴化 (categorification)：构造一族分次阿贝尔群——Khovanov 同调 $K{h}^{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$（符号安排的相容性需要验证，这是构造的技术核心）。
• 同调：

$$K{h}^{i,j}=\ker d_{i,j}/\mathrm{im}{d}_{i-1,j},$$

闭链模边缘链。分次 Euler 特征标 ${\sum }_{i,j}(-1{)}^i{q}^j\dim K{h}^{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^{†}d+d{d}^{†},$$

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

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

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

$$0=⟨c,\Delta c⟩=⟨c,d^{†}dc⟩+⟨c,d{d}^{†}c⟩=⟨dc,dc⟩+⟨d^{†}c,d^{†}c⟩=\Vert dc{\Vert }^2+\Vert d^{†}c{\Vert }^2.$$

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

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

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

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

1. 可热化：$\Delta$ 的 Gibbs 态能在多项式时间内制备（典型 Gibbs 制备的障碍——谱隙、温度、与环境的耦合设计——这里全部内嵌于“thermalize”一词，见 Gibbs 态词条的讨论）；
2. 谱隙：零空间（严格说零特征值簇）与其余谱之间有 $\ge 1/\mathrm{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)=AI+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 编译为 $\mathrm{poly}(m,n,k)$ 的局部酉电路（因子 $m,n,k$ 的来源逐项清点于第 4.4 节）。
• Plat closure = 矩阵元：Hadamard test 以 $\Theta (1/{ϵ}^2)$ 采样（Hoeffding）或振幅估计 $O(1/ϵ)$ 给出 $⟨\alpha |U_b|\alpha ⟩$ 的加性 $ϵ$ 估计；Jones 值的误差是 $|C(b,k)|ϵ$——加性、非相对、非精确，且 $|C|$ 可指数大（第 5.4 节）。
• Trace closure = Markov trace：终点权重 $\pi (p)\propto {\lambda }_{p_n}$ 的加权归一化迹（Markov 定理迫使的形状）；可经提纯态一次 Hadamard test 估计，或两阶段抽样（第 6.2 节给出 $s^{\ast }={\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^{†}d+d{d}^{†}$ 的近零谱质量（$\ker \Delta \cong$ 同调，Lemma 6），以预热化克服“秩 $\ll$ 维数”，高效性依赖多项式热化与谱隙承诺；秩的加性近似按精度分为 DQC1-hard / BQP-hard / $\#\mathsf{P}$-hard 三档。

习题。

1. **（TL 图示演算）**画图验证第 3.1 节的三条 TL 关系：(a) 对 $e_i^2=d{e}_i$，数出堆叠中封闭圈的个数并说明为何恰好是一个；(b) 对 $e_i{e}_{i+1}{e}_i=e_i$，追踪三条外侧股的连通情况，说明中间为何没有产生封闭圈；(c) 用 (a)(b) 复核第 3.3 节 Lemma 3 展开中 $u^2=du$ 与 $uvu=u$ 的每次使用。
2. **（计算）**沿第 8 节的方法计算 ${\rho }_A({\sigma }_1^4)$（提示：$(A+A^{-1}e{)}^4=A^4+({\sum }_{j=1}^4\left(\genfrac{}{}{0ex}{}{4}{j}\right)A^{4-2j}{d}^{j-1})e$，逐项写出）与 $⟨\widehat{{\sigma }_1^4}⟩$，并求 trace closure（$(2,4)$ 环面链环）的 Jones 值在 $t=e^{2\pi i/6}$ 处的显式复数。再用 $V_{\widehat{{\sigma }_1^2}}=-i$ 与 skein 关系 $t^{-1}{V}_{L_{+}}-t{V}_{L_{-}}=(t^{1/2}-t^{-1/2})V_{L_0}$ 核对你的答案。
3. **（采样置信度）**第 5.3 节用 Hoeffding 不等式得到常数置信度下 $K=\Theta (1/{ϵ}^2)$。若要求置信度 $1-{\delta }_{\mathrm{conf}}$，写出 $K$ 关于 $ϵ$ 与 ${\delta }_{\mathrm{conf}}$ 的完整表达式，并解释为什么对 ${\delta }_{\mathrm{conf}}$ 的依赖只是对数级的（联系振幅估计中“失败重试”的标准论证）。
4. **（两阶段平衡）**在第 6.2 节的两阶段方案中，设 ${\sigma }_{\pi }=3$、$c=1$、总预算 $N=10^6$ 次电路运行。求最优的 $s^{\ast },K^{\ast }$ 与相应的总误差；若把预算提高为 $4N$，误差改善多少？由此说明“把样本在两个阶段间按 ${\sigma }_{\pi }:c$ 分配、使两项误差同阶”的含义。
5. **（误差尺度）**设某链环的 $|C(b,k)|=2^{m/2}$、而 $|J|\approx 1$。(a) 要让加性估计足以判断 $J$ 的符号，$ϵ$ 需多小？采样复杂度随 $m$ 如何增长？(b) 由此解释为什么“加性近似 BQP-complete”与“相对误差近似可能需要指数资源”并不矛盾，并说明这与第 5.4 节、第 9.3 节两处保留条款的关系。
6. **（概念辨析）**分别给出以下三个量能区分、而前一个不能区分的链环例子或论证方向：(a) Jones 多项式 vs Khovanov 分次 Euler 特征标（它们何时给出相同信息？）；(b) Euler 特征标 vs Khovanov 同调群（提示：同一组分次维数可以给出相同 Euler 特征标而群结构不同；再想想“识别平凡结”的性质落在哪一侧）；(c) 结合第 9.2 节的三档硬度阶梯，说明“把秩估计到越来越准”为什么在每个档位上落进不同的复杂度类。

参考文献与 Zoo 覆盖

• Zoo 2、4、41、42：Aharonov—Jones—Landau 与 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 量子算法。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch13-topology-statistical-physics/knot-invariants
• 内容遵循 CC BY-NC-SA 4.0 许可协议