2025-11-16T06:46:12.290457

Towards a complexity-theoretic dichotomy for TQFT invariants

Bridges, Samperton

We show that for any fixed $(2+1)$-dimensional TQFT over $\mathbb{C}$ of either Turaev-Viro-Barrett-Westbury or Reshetikhin-Turaev type, the problem of (exactly) computing its invariants on closed 3-manifolds is either solvable in polynomial time, or else it is $\#\mathsf{P}$-hard to (exactly) contract certain tensors that are built from the TQFT's fusion category. Our proof is an application of a dichotomy result of Cai and Chen [J. ACM, 2017] concerning weighted constraint satisfaction problems over $\mathbb{C}$. We leave for future work the issue of reinterpreting the conditions of Cai and Chen that distinguish between the two cases (i.e. $\#\mathsf{P}$-hard tensor contractions vs. polynomial time invariants) in terms of fusion categories. We expect that with more effort, our reduction can be improved so that one gets a dichotomy directly for TQFTs' invariants of 3-manifolds rather than more general tensors built from the TQFT's fusion category.

academic

Towards a complexity-theoretic dichotomy for TQFT invariants

基本信息

论文ID: 2503.02945
标题: Towards a complexity-theoretic dichotomy for TQFT invariants
作者: Nicolas Bridges, Eric Samperton
分类: math.QA cs.CC math.GT quant-ph
发表时间: March 6, 2025 (arXiv预印本)
论文链接: https://arxiv.org/abs/2503.02945

摘要

本文证明了对于任何固定的 $(2+1)$ 维复数域上的TQFT（拓扑量子场论），无论是Turaev-Viro-Barrett-Westbury类型还是Reshetikhin-Turaev类型，在闭3-流形上精确计算其不变量的问题要么可以在多项式时间内求解，要么从TQFT的融合范畴构建的某些张量收缩是 $\#\mathsf{P}$ -困难的。证明基于Cai和Chen关于复数域上加权约束满足问题的二分性结果。作者将重新解释Cai-Chen条件以融合范畴术语的工作留给未来研究，并期望通过进一步努力，可以改进约化方法，直接获得TQFT 3-流形不变量的二分性。

研究背景与动机

问题背景

拓扑量子计算的复杂性分类：该研究源于拓扑量子计算中对"任意子系统"的分类问题，即确定哪些任意子系统足够强大，能够（近似）编码任意量子比特电路。
Property F猜想：Naidu和Rowell提出的Property F猜想是该领域唯一具体的分类答案：在酉模张量范畴中，简单任意子X的n个副本的可能编织仅产生有限多个酉算子（因此不是"编织通用的"），当且仅当X的量子维数的平方是整数。
复杂性理论中的二分性定理：在复杂性理论中，二分性定理表明某些问题族要么"容易"（P类），要么"困难"（NP-困难），不存在中间复杂度。Schaefer的布尔可满足性二分性定理是这类结果的典型例子。

研究动机

本文的核心动机是将复杂性理论的二分性概念应用到TQFT不变量的计算中，为任意子分类问题提供复杂性理论视角。这种方法可能为理解Property F猜想的变体提供新的洞察。

核心贡献

建立TQFT不变量的复杂性二分性：证明了对于固定的球面融合范畴C或模融合范畴B，相应的TQFT不变量计算要么在多项式时间内可解，要么相关张量收缩是 $\#\mathsf{P}$ -困难的。
将Cai-Chen二分性定理应用于TQFT：首次将加权约束满足问题的二分性结果应用到拓扑量子场论的计算复杂性分析中。
构造多项式时间约化：提供了从3-流形编码到约束满足问题实例的多项式时间约化算法。
为任意子分类提供新视角：从复杂性理论角度为任意子分类问题提供了新的理论框架。

方法详解

任务定义

本文研究两类TQFT不变量的计算复杂性：

输入：闭定向3-流形M（通过三角剖分或手术图表示）
输出：TQFT不变量 $|M|_C$ （TVBW类型）或 $\tau_B(M)$ （RT类型）
目标：确定计算是多项式时间可解还是 $\#\mathsf{P}$ -困难

核心定理

定理1：

(a) 对于固定的球面融合范畴C，要么TVBW不变量 $|M|_C$ 在多项式时间内可计算，要么 $\#CSP(F_C)$ 是 $\#\mathsf{P}$ -困难的。
(b) 对于固定的模融合范畴B，要么RT不变量 $\tau_B(M)$ 在多项式时间内可计算，要么 $\#CSP(F_B)$ 是 $\#\mathsf{P}$ -困难的。

技术方法

1. Cai-Chen二分性定理的应用

利用Cai和Chen的结果：对于任何约束集合F， $\#CSP(F)$ 要么多项式时间可解，要么 $\#\mathsf{P}$ -困难。

2. 约束满足问题的构造

定义： $\#CSP(F)$ 问题包括：

有限域 $D = \{1, \ldots, d\}$
加权约束族 $F = \{f_1, \ldots, f_h\}$ ，其中 $f_i: D^{r_i} \to \mathbb{C}$
实例I由变量元组和约束元组组成
输出： $Z(I) = \sum_{x \in D^n} F_I(x)$

3. TVBW不变量的约化（定理1(a)的证明）

状态求和公式： $|M|_C = D^{-2|V_M|} \sum_{L:E_M \to \text{Irr}(C)} \prod_{e \in E_M} \dim(L(e))^2 \prod_{t \in T_M} |t^L| \prod_{f \in F_M} |f^L|$

约束函数构造：

域： $D_C = \text{Irr}(C) \sqcup N \sqcup \{*\}$
6j+4k符号： $\Delta^{\pm}$ （10元函数）
3j+1k符号： $\Phi^{-1}$ （4元函数）
量子维数： $d^2$ （1元函数）
总量子维数： $D^{-2}$ （1元函数）

约化算法：

为每个顶点、边、面分配变量
为每个顶点添加 $D^{-2}$ 函数
为每个边添加 $d^2$ 函数
为每个面添加 $\Phi^{-1}$ 函数
为每个四面体添加 $\Delta^{\pm}$ 函数（符号取决于定向）

4. RT不变量的约化（定理1(b)的证明）

RT不变量公式： $\tau_B(M) = p_+^{\frac{\sigma(L)-m-1}{2}} p_-^{\frac{-\sigma(L)-m-1}{2}} \sum_{\text{col}} \left(\prod_{j=1}^m \dim(\text{col}(j))\right) |L^{\text{col}}|$

关键技术引理： 引理4：对于 $S^2$ 中的闭三价图 $\Gamma$ ，存在多项式时间算法构造图序列 $\Gamma_0, \Gamma_1, \ldots, \Gamma_l$ ，其中 $\Gamma_0 = \Gamma$ ， $\Gamma_l = \emptyset$ ，每个 $\Gamma_{i+1}$ 通过标准图操作从 $\Gamma_i$ 得到。